Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to construct a binary tree using a level order traversal sequence

How to construct a binary tree using a level order traversal sequence, for example from sequence {1,2,3,#,#,4,#,#,5}, we can construct a binary tree like this:

     1
    / \
   2   3
      /
     4
      \
       5

where '#' signifies a path terminator where no node exists below.

Finally I implement Pham Trung's algorithm by c++

struct TreeNode
{
    TreeNode *left;
    TreeNode *right;
    int val;

    TreeNode(int x): left(NULL), right(NULL), val(x) {}
};
TreeNode *build_tree(char nodes[], int n)
{
    TreeNode *root = new TreeNode(nodes[0] - '0'); 
    queue<TreeNode*> q;
    bool is_left = true;
    TreeNode *cur = NULL;
    q.push(root);

    for (int i = 1; i < n; i++) {
        TreeNode *node = NULL;
        if (nodes[i] != '#') {
            node = new TreeNode(nodes[i] - '0');
            q.push(node);
        }

        if (is_left) {
            cur = q.front();
            q.pop();
            cur->left = node;
            is_left = false;
        } else {
            cur->right = node;
            is_left = true;
        }
    }

    return root;
}
like image 467
bigpotato Avatar asked May 20 '14 07:05

bigpotato


People also ask

Can we construct tree from level order traversal?

we can build this binary tree from level order traversal by maintaining a queue. Queue is used to maintain those nodes that are not yet processed. Using a variable count(index variable) to keep track of the number of children added for the current node. First, create a root node, assign it as the current node.

Which traversal sequence is used to construct a binary tree?

Inorder and Level-order.

How can we perform level order traversal on a tree?

Trees can also be traversed in level order, where we visit every node on a level before going to a lower level. This search is referred to as level order traversal or Breadth–first search (BFS), as the search tree is broadened as much as possible on each depth before going to the next depth.


1 Answers

Assume using array int[]data with 0-based index, we have a simple function to get children:

  • Left child

      int getLeftChild(int index){
         if(index*2 + 1 >= data.length)
            return -1;// -1 Means out of bound
         return data[(index*2) + 1];
      }
    
  • Right child

      int getRightChild(int index){
         if(index*2 + 2 >= data.length)
            return -1;// -1 Means out of bound           
         return data[(index*2) + 2];
      }
    

Edit: Ok, so by maintaining a queue, we can build this binary tree.

We use a queue to maintain those nodes that are not yet processed.

Using a variable count to keep track of the number of children added for the current node.

First, create a root node, assign it as the current node. So starting from index 1 (index 0 is the root), as the count is 0, we add this node as left child of the current node. Increase count. If this node is not '#', add it to the queue.

Moving to the next index, the count is 1, so we add this as right child of current node, reset count to 0 and update current node (by assigning the current node as the first element in the queue). If this node is not '#', add it to the queue.

     int count = 0;
     Queue q = new Queue();
     q.add(new Node(data[0]);
     Node cur = null;
     for(int i = 1; i < data.length; i++){
        Node node = new Node(data[i]);
        if(count == 0){
           cur = q.dequeue();           
        }
        if(count==0){
          count++;
          cur.leftChild = node;
        }else {
          count = 0;
          cur.rightChild = node;
        }
        if(data[i] != '#'){
          q.enqueue(node);
        }
     }    



    class Node{
       int data;
       Node leftChild, rightChild;
    } 

Note: this should only work for a binary tree and not BST.

like image 101
Pham Trung Avatar answered Oct 22 '22 12:10

Pham Trung