Menu
What is the time complexity of binary tree level order traversal ? Is it O(n) or O(log n)?
void levelorder(Node *n)
{ queue < Node * >q;
q.enqueue(n);
while(!q.empty())
{
Node * node = q.front();
DoSmthwith node;
q.dequeue();
if(node->left != NULL)
q.enqueue(node->left);
if (node->right != NULL)
q.enqueue(node->right);
}
}
925
The binary search tree is a balanced binary search tree. Height of the binary search tree becomes log(n). So, Time complexity of BST Operations = O(logn).
A Level Order Traversal is a traversal which always traverses based on the level of the tree. So, this traversal first traverses the nodes corresponding to Level 0, and then Level 1, and so on, from the root node.
Introduction to level order traversalIn the short form, we also call it BFS traversal. A binary tree is organized in different levels where root node is at the topmost level (0th level).
Use DFS to traverse the tree and maintain height for the current node. Recursively call to for tree->left, level-1. Recursively call to for tree->right, level-1.
It is O(n), or to be exact Theta(n).
Have a look on each node in the tree - each node is "visited" at most 3 times, and at least once) - when it is discovered (all nodes), when coming back from the left son (non leaf) and when coming back from the right son (non leaf), so total of 3*n visits at most and n visites at least per node. Each visit is O(1) (queue push/pop), totaling in - Theta(n).
88
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
