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

Question

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:

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;
}

Pham Trung · Accepted Answer · 2021-07-06 12:14:19Z

12

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.

edited Jul 6, 2021 at 12:14

answered May 20, 2014 at 8:14

Pham Trung

11.3k2 gold badges26 silver badges43 bronze badges

Sign up to request clarification or add additional context in comments.

16 Comments

bigpotato Over a year ago

you see ,in the array {1,2,3,#,#,4,#,#,5}, element 4's left child should be # and 5, but 4's index is 5, #'s index is 7, 5's index is 8

Pham Trung Over a year ago

@bigpotato can you describe more about your array? How to know which element is whose child? normally, mine is how an array represent a binary tree.

bigpotato Over a year ago

please look at the description of my question, there is an example

Pham Trung Over a year ago

@bigpotato so please set it as answer for the question :)

Pham Trung Over a year ago

@mahee96 done, oh yes, I also missed that point about BST from your earlier comment, should have saved us some time. Glad that we both learned smt!

|

Dekay · Accepted Answer · 2020-03-27 16:54:24Z

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. So starting from index 1, index value is 1 means, we will add the next value as left node. index value is 2 means we will add the next value as right node and index value 2 means that we have added left and right node, then do the same for the remaining nodes.

if arr value is -1

3.a. if index value is 1,i.e., there is no left node then change the index variable to add right node.
3.b. if index value is 2, i.e, there is no right node then we have repeat this step for the remaining.

static class Node{
    int data;
    Node left;
    Node right;
    Node(int d){
        data=d;
        left=null;
        right=null;
    }
}

public static Node constBT(int arr[],int n){

    Node root=null;
    Node curr=null;
    int index=0;
    Queue<Node> q=new LinkedList<>();
    for(int i=0;i<n;i++){

        if(root==null){
            root=new Node(arr[i]);
            q.add(root);
            curr=q.peek();
            index=1;
        }else{
            if(arr[i]==-1){

                 if(index==1)
                    index=2;
                else{
                    q.remove();
                    curr=q.peek();
                    index=1;

                }
            }

            else if(index==1){
                curr.left=new Node(arr[i]);
                q.add(curr.left);
                index=2;

            }else if(index==2){
                curr.right=new Node(arr[i]);
                q.add(curr.right);
                q.remove();
                curr=q.peek();
                index=1;
            }

        }
    }
    return root;
}

TAZRIL ALI · Accepted Answer · 2020-11-09 08:38:14Z

My approach is similar to Pham Trung yet intutive. We would maintain an array of Nodes of given data instead of using a queue. We would do reverse engineering on BFS using queue. because BFS for a tree is basically its Level Order Traversal (LOT).

It is important to note that we should have the NULL childs of an node for the LOT to be unique and the reconstruction of Tree from LOT to be possible.

In this case LOT : 1,2,3,-1,-1,4,-1,-1,5
where I have used -1 instead of '#' to represent NULLs
And Tree is

Here, we can easily see that when 1 is popped from the BFS queue, it pushed its left child (2) and right child (3) in the queue. Similary, for 2 it pushed -1 (NULL) for both of its children. And the process is continued.
So, we can follow the following pseudo code to generate the tree rooted at LOT[0]

j = 1
For every node in LOT:
  if n<=j: break
  if node  != NULL:
    make LOT[j] left child of node 
    if n<=j+1: break
    make LOT[j+1]  right child of node
  j <- j+2

Finally, C++ code for the same
Class Declaration and Preorder traversal

class Node{
public:
    int val;
    Node* lft, *rgt;
    Node(int x ):val(x) {lft=rgt=nullptr;}
};


void preorder(Node* root) {
    if(!root)   return;
    cout<<root->val<<" ";
    preorder(root->lft);
    preorder(root->rgt);
}

Restoring Tree from LOT Logic


int main(){
    int arr[] = {1,2,3,-1,-1,4,-1,-1,5};
    int n = sizeof(arr)/sizeof(int);
    Node* brr[n];
    for(int i=0;i<n;i++)  {
        if(arr[i]==-1)  brr[i] = nullptr;
        else brr[i] = new Node(arr[i]);
    }
    for(int i=0,j=1;j<n;i++) {
        if(!brr[i]) continue;
        brr[i]->lft = brr[j++];
        if(j<n) brr[i]->rgt = brr[j++];
    }
    preorder(brr[0]);
}

Output: 1 2 3 4 5

Collectives™ on Stack Overflow

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

3 Answers 3

16 Comments

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.

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

16 Comments

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.

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related