Binary tree traversal: Preorder, Inorder, Post-order, BFS, DFS, Level Order, zig zag order

In order to illustrate the 3 traversals  - pre order, in-order and post-order lets take following tree:

Preorder traversal:
To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Implementing pre-order traversal

preorder(N *root)
{
  if(root)
  {
    printf("Value : [%d]", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

More details here.


Inorder traversal:
Inorder traversal prints the binary tree in increasing order. To traverse a binary tree in Inorder, following operations are carried-out (i) Traverse the left most subtree starting at the left external node, (ii) Visit the root, and (iii) Traverse the right subtree starting at the left external node.
Consider the tree below

Therefore, the Inorder traversal of the above tree will outputs:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Implementing inorder traversal(recursive)

inorder(Node *root)
{
  if(root)
  {
    inorder(root->left);
    printf("Value : [%d]", root->value);
    inorder(root->right);
  }
}

More details here.  

Postorder traversal:
To traverse a binary tree in Postorder, following operations are carried-out (i) Traverse all the left external nodes starting with the left most subtree which is then followed by bubble-up all the internal nodes, (ii) Traverse the right subtree starting at the left external node which is then followed by bubble-up all the internal nodes, and (iii) Visit the root.

Consider the tree below

Therefore, the Postorder traversal of the above tree will outputs:
0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Implementing post order traversal

postorder(Node *root)
{
  if(root)
  {
    postorder(root->left);
    postorder(root->right);
    printf("Value : [%d]", root->value);
  }
}

More details here.
Time complexity of above traversals is O(n).

BFS-Breadth first search
This is same as level order traversal, where we go level by level of the tree.

more details here.

DFS - Depth first search
more details here.

Level order traversal

Zig-zag order traversal

more details here.

Read More

Construct a full binary tree from a pre-order list of marked nodes

Question: construct a full binary tree from a list of nodes in pre-order. The nodes are marked 'i' if they are inner nodes and are marked 'l' if they are leaf nodes.
Example given a list of nodes marked as (i, i, i, l, l, i, l, l, i, l, l), we need to construct a tree from those nodes so that the result looks like this:






Notice how all "l" nodes are leaf nodes and "i" nodes are inner nodes? Moreover, since the nodes are given in pre-order, we must take into account the node order when we put them into the tree. The first node in the list will always be the root node because in pre-order, root node comes first then left most and then right most. Also, since this is a full binary tree, we know that every node, except leaf node, must have 2 children.
With the information provided by the question, here is the code to solve this problem:

#include<iostream>
#include<stack>
using namespace std;

struct Node
{
  Node* left;
  Node* right;
  char mark;
};

Node* constructFromPreorder(Node* preorder[], int treeSize)
{
  stack<Node*> stackOfNodes;

  Node* root = preorder[0]; //pointer to root node
  
  stackOfNodes.push(preorder[0]);

  int count = 1;
  
  while (count < treeSize && !stackOfNodes.empty())
  {
    if (stackOfNodes.top()->left == NULL || stackOfNodes.top()->right == NULL)
    {
      Node* currentNode = preorder[count];
      
      if (stackOfNodes.top()->left == NULL)
        stackOfNodes.top()->left = currentNode;
      else if (stackOfNodes.top()->right == NULL)
        stackOfNodes.top()->right = currentNode;

      if (currentNode->mark == 'i')
        stackOfNodes.push(currentNode);
        
      count++;
    }
    else
    {
      stackOfNodes.pop();
    }
  }

  return root;
}

Explanation: assuming that we have the Node struct like the one in the code, then the left pointer of a node points to the left child of that node while the right pointer points to the right child. Hence, we can now put those nodes in a tree by connecting parent nodes to child nodes.

1. Declare a stack to keep track of inner nodes. Whenever we encounter an inner node, we'll push it into the stack. And, we'll pop it when it has two children. This makes sure that every inner node is connected to its two children.
2. Add the root which is the first node in the list into the stack. Because we'll add and push the nodes until the stack is empty or until we run out of nodes, we need to add the root to initialize the stack.
3. Set a count flag to 1. This count flag is used to exit the loop. When count reaches the total number of nodes in the list, it means we've run out of nodes to add into our tree. Moreover, we initialize the flag to 1 since we have already processed one node(root node) from the list in step 2.
4. Loop until either we run out of nodes to add or until the stack is empty.
5. For every loop:
   
   a) If the top of the stack is not connected to its two children yet, we get a node out of our list and attach it to the top node in the stack as that node's child. Then, we push that newly retrieved node into the stack if it is an inner node. We also increase the count flag by 1, so we can retrieve the next node in the list in the next loop.
   
   b) If the top of the stack has already been connected to two children, we pop it and do nothing.
   
   
6. When the loop is done, we simply return the pointer to the root. Whichever function uses this pointer will have access to the entire tree that we have just constructed.

Performance: this algorithm has time complexity of O(n) where n is the number of nodes in the list because we loop through the list only once. In terms of space, the algorithm has space complexity of O(m) where m is the depth of the tree we have to construct. The reason is that in the worst case we must store the second-deepest nodes into our stack.

Read More

Construct a tree given its inorder and preorder traversal strings. Similarly construct a tree given its inorder and post order traversal strings.

For Inorder And Preorder traversals


inorder  = g d h b e i a f j c
preorder = a b d g h e i c f j

Scan the preorder left to right using the inorder sequence to separate left and right subtrees. For example, "a" is the root of the tree; "gdhbei" are in the left subtree; "fjc" are in the right subtree. "b" is the next root; "gdh" are in the left subtree; "ei" are in the right subtree. "d" is the next root; "g" is in the left subtree; "h" is in the right subtree.




For Inorder and Postorder traversals

Scan postorder from right to left using inorder to separate left and right subtrees.


inorder   = g d h b e i a f j c
postorder = g h d i e b j f c a

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.



For Inorder and Levelorder traversals

Scan level order from left to right using inorder to separate left and right subtrees.



inorder     = g d h b e i a f j c
level order = a b c d e f g h i j

Tree root is "a"; "gdhbei" are in left subtree; "fjc" are in right subtree.


Here is some working code which creates a tree out of the Inorder and Postorder traversals. Note that here the tree has been represented as an array. This really simplifies the whole implementation.

Converting a tree to an array is very easy.

Suppose we have a tree like this


      A
  B       C
D   E   F   G

The array representation would be


a[1] a[2] a[3] a[4] a[5] a[6] a[7]
  A    B    C    D    E    F    G

That is, for every node at position j in the array, its left child will be stored at position (2*j) and right child at (2*j + 1). The root starts at position 1.

// CONSTRUCTING A TREE GIVEN THE INORDER AND PREORDER SEQUENCE

#include <stdio.h>
#include <string.h>
#include <ctype.h>

/*-------------------------------------------------------------
* Algorithm
*
* Inorder And Preorder
* inorder = g d h b e i a f j c
* preorder = a b d g h e i c f j
* Scan the preorder left to right using the inorder to separate left
* and right subtrees. a is the root of the tree; gdhbei are in the
* left subtree; fjc are in the right subtree.
*------------------------------------------------------------*/

static char io[]="gdhbeiafjc";
static char po[]="abdgheicfj";
static char t[100][100]={'\0'};  //This is where the final tree will be stored
static int hpos=0;

void copy_str(char dest[], char src[], int pos, int start, int end);
void print_t();

int main(int argc, char* argv[])
{
  int i,j,k;
  char *pos;
  int posn;

  // Start the tree with the root and its
  // left and right elements to start off

  for(i=0;i<strlen(io);i++)
  {
     if(io[i]==po[0])
     {
        copy_str(t[1],io,1,i,i);             // We have the root here
        copy_str(t[2],io,2,0,i-1);           // Its left subtree
        copy_str(t[3],io,3,i+1,strlen(io));  // Its right subtree
        print_t();
     }
  }

  // Now construct the remaining tree
  for(i=1;i<strlen(po);i++)
  {
     for(j=1;j<=hpos;j++)
     {
        if((pos=strchr((const char *)t[j],po[i]))!=(char *)0 && strlen(t[j])!=1)
        {
            for(k=0;k<strlen(t[j]);k++)
            {
               if(t[j][k]==po[i]){posn=k;break;}
            }
            printf("\nSplitting [%s] for po[%d]=[%c] at %d..\n", t[j],i,po[i],posn);

            copy_str(t[2*j],t[j],2*j,0,posn-1);
            copy_str(t[2*j+1],t[j],2*j+1,posn+1,strlen(t[j]));
            copy_str(t[j],t[j],j,posn,posn);
            print_t();
        }
     }
  }
}

// This function is used to split a string into three seperate strings
// This is used to create a root, its left subtree and its right subtree

void copy_str(char dest[], char src[], int pos, int start, int end)
{
  char mysrc[100];
  strcpy(mysrc,src);
  dest[0]='\0';
  strncat(dest,mysrc+start,end-start+1);
  if(pos>hpos)hpos=pos;
}


void print_t()
{
  int i;
  for(i=1;i<=hpos;i++)
  {
    printf("\nt[%d] = [%s]", i, t[i]);
  }
  printf("\n");
}







Read More

Pre Order traversal - Recursive and Iterative solution

Example
Consider the tree:
div class="separator" style="clear: both; text-align: center;">

To traverse a binary tree in Preorder, following operations are carried-out (i) Visit the root, (ii) Traverse the left subtree, and (iii) Traverse the right subtree.
Therefore, the Preorder traversal of the above tree will outputs:
7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

Recursive solution

preorder(N *root)
{
  if(root)
  {
    printf("Value : [%d]", root->value);
    preorder(root->left);
    preorder(root->right);
  }
}

Iterative solution

In some ways this is the simplest to understand initially.  However, even though each node is processed before the subtrees, it still requires that some information be retained while moving down the tree.  In the example
above, the * is processed first, then the left sub-tree followed by the right subtree.  Therefore, processing must return to the right sub-tree after finishing the processing of the left subtree.

In the examples given, suppose the the processing involved in the traversal is to print out the information stored in each node.Since movement is down the left side of the tree beginning at the root, information on what is to the right must be kept in order to complete the traversal of the right side of any subtree.  The obvious ADT for such information is a stack.   Because of its LIFO structure, it will be possible to get the information about the right subtrees back in the reverse order in which it was encountered.

The process of doing a pre-order traversal iteratively then has the following steps (assuming that a stack is available to hold pointers to the appropriate nodes):

1. push NULL onto the stack
2. start at the root and begin execution
3. write the information in the nodeN
4. if the nodeN-> right != NULL , push the pointer onto the stack
We push right one first as we need it last
5. if the nodeN -> left !=  NULL move the pointer to the node on the left
6. if the nodeN->left == NULL pop the stack
7. repeat steps 3 to 7 until no nodes remain


Using array indirectly as stack

void iterativePreorder(node *root)
{
 node *save[100];
 int top = 0;
 if (root == NULL)
 {
  return;
 }

 save[top++] = root;
 
 while (top != 0)
 {
  root = save[--top];
  printf("[%d] ", root->value);
  if (root->right != NULL)
   save[top++] = root->right;
   if (root->left != NULL)
    save[top++] = root->left;
 }
}

Using proper stack ( for clarity)

void preOrderNonRecursive(node* root) {
    if (!root) {
       return;
    }
    Stack<node*> t = new Stack<node*>();
    t.Push(root);
    while (t.Size() > 0) {
        node* top = t.Pop();
        printf("%d", top->value);
        if (top->right != null) {
            t.Push(top->right);
        }
        if (top->left != null) {
            t.Push(top->left);
        }
    }
}

Running the dry run on the above tree :
push root
stack 6

pop 6, push 8 2
stack 8 2

pop 2, push 5, 1
stack 8 5 1

pop 1,
stack 8 5

pop 5,
stack 8

pop 8, push 7
stack 7

pop 7

So have a look at all pop-order
6 2 1 5 8 7

Read More