[go: up one dir, main page]
Scribd
Upload
56 views4 pages

Level Order Traversal of Binary Tree - Techie Delight

The document describes four different methods for traversing and printing the nodes of a binary tree: level order traversal, which prints each level from left to right; spiral order traversal, which alternates between left to right and right to left at each level; reverse level order traversal, which prints each level in reverse order using a stack; and printing all nodes by level using two queues, one for each half of each level.

Uploaded by

akg299
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
56 views4 pages

Level Order Traversal of Binary Tree - Techie Delight

The document describes four different methods for traversing and printing the nodes of a binary tree: level order traversal, which prints each level from left to right; spiral order traversal, which alternates between left to right and right to left at each level; reverse level order traversal, which prints each level in reverse order using a stack; and printing all nodes by level using two queues, one for each half of each level.

Uploaded by

akg299
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 4

Level Order Traversal of Binary Tree - Techie Delight

void levelOrderTraversal(Node* root)


{
if (root == nullptr)
return;

// create an empty queue and enqueue root node


list<Node*> queue;
queue.push_back(root);

// pointer to store current node


Node* curr = nullptr;

// run till queue is not empty


while (queue.size())
{
// process each node in queue and enqueue their
// non-empty left and right child to queue
curr = queue.front();
queue.pop_front();

cout << curr->key << " ";

if (curr->left)
queue.push_back(curr->left);

if (curr->right)
queue.push_back(curr->right);
}
}
Spiral Order Traversal of Binary Tree - Techie Delight
void spiralOrderTraversal(Node* root)
{
if (root == nullptr)
return;

// create an empty double ended queue and push root node


list<Node*> deque; // or use deque
deque.push_front(root);

// flag used to differentiate between odd or even level


bool flag = false;

// run till deque is not empty


while (!deque.empty())
{
// calculate number of nodes in current level
int nodeCount = deque.size();

// print left to right


if (flag)
{
// process each node of current level and push their
// non-empty left and right child to deque
while (nodeCount)
{
// pop from front if flag is true
Node* curr = deque.front();
deque.pop_front();

cout << curr->key << " ";

// push left child to end followed by right child


// if flag is true

if (curr->left != nullptr)
deque.push_back(curr->left);

if (curr->right != nullptr)
deque.push_back(curr->right);

nodeCount--;
}
}

// print right to left


else
{
// process each node of current level and push their
// non-empty right and left child to queue
while (nodeCount)
{
// Important - pop from back if flag is false
Node* curr = deque.back();
deque.pop_back();

cout << curr->key << " "; // print front node

// Important - push right child to front followed by left


// child if flag is false

if (curr->right != nullptr)
deque.push_front(curr->right);

if (curr->left != nullptr)
deque.push_front(curr->left);

nodeCount--;
}
}

// flip the flag for next level


flag = !flag;
cout << endl;
}
}
Reverse Level Order Traversal of Binary Tree - Techie Delight
void reverseLevelOrderTraversal(Node* root)
{
if (root == nullptr)
return;

// create an empty queue and enqueue root node


list<Node*> queue;
queue.push_back(root);

// create an stack to reverse level order nodes


stack<int> stack;

// pointer to store current node


Node* curr = nullptr;

// run till queue is not empty


while (queue.size())
{
// process each node in queue and enqueue their children
curr = queue.front();
queue.pop_front();

// push current node to stack


stack.push(curr->key);

// important - process right node before left node


if (curr->right)
queue.push_back(curr->right);

if (curr->left)
queue.push_back(curr->left);
}

// pop all nodes from the stack and print them


while (!stack.empty())
{
cout << stack.top() << " ";
stack.pop();
}
}

Print all nodes of a given binary tree in specific order - Techie Delight
void printNodes(Node* root)
{
// return is tree is empty
if (root == nullptr)
return;

// print root node


cout << root->key << " ";

// create an two empty queues and enqueue root's left and


// right child respectively
queue<Node *> Q1, Q2;
Q1.push(root->left);
Q2.push(root->right);

// run till queue is not empty


while (!Q1.empty())
{
// calculate number of nodes in current level
int n = Q1.size();

// process every node of current level


while (n--)
{
// pop front node from first queue and print it
Node* x = Q1.front();
Q1.pop();

cout << x->key << " ";

// push left and right child of x to first queue


if (x->left)
Q1.push(x->left);

if (x->right)
Q1.push(x->right);

// pop front node from second queue and print it


Node* y = Q2.front();
Q2.pop();

cout << y->key << " ";

// push right and left child of y to second queue


if (y->right)
Q2.push(y->right);

if (y->left)
Q2.push(y->left);
}
}
}

You might also like