How to construct a binary tree from level order array?

Question

I'm working on a coding question and right now I'm bit confused. If I'm given an array which represents level order traversal of a binary tree. How do I construct a tree from that?

So far here is my thought process so far: I know the 0th index is the root, leftChild = 2*i+1 and rightChild = 2*i+2.

Here is what I have so far and I don't think its right:

public Tree buildTree(ArrayList<Tree> arr, int i) {
    if (i > list.size() - 1) {
        return null;
    }

    root = list.get(i);
    root.LeftChild = buildTree(arr, 2*i+1);
    root.RightChild = buildTree(arr, 2*i+2);

    return root;
}

my i starts at 0, Thanks.

Can you provide link to the question ?

zenwraight
– zenwraight

2018-10-29 01:38:29 +00:00
Commented Oct 29, 2018 at 1:38 — zenwraight
– zenwraight, Commented Oct 29, 2018 at 1:38

Shanu Gupta · Accepted Answer · 2018-10-29 09:11:52Z

2

Your code would only work with complete binary trees, a special case of binary trees.

You can't construct generic binary tree just from the level order traversal.

You need two traversal of which one must be an inorder traversal.

Following combination can uniquely identify a tree.

Inorder and Preorder.
Inorder and Postorder.
Inorder and Level-order.

Though there is a possibility to construct tree (given only level order traversal) if you've some separators in the given array like described in this post.

edited Oct 29, 2018 at 9:11

answered Oct 29, 2018 at 7:02

Shanu Gupta

3,8272 gold badges21 silver badges29 bronze badges

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

2 Comments

Rocky Singh Over a year ago

It is a complete binary tree

Shanu Gupta Over a year ago

@RockySingh your code seems to work fine for complete binary tree. Did you tried the edge cases like tree with 0,1, half complete, fully complete nodes?

Victor Cui · Accepted Answer · 2018-10-29 02:36:06Z

0

Your code seems fine...although it's strange that your method takes in an ArrayList<Tree> instead of an ArrayList<Node>. Why don't you think it's right? How are you testing your method? What kind of errors are you getting?

answered Oct 29, 2018 at 2:36

Victor Cui

1,7435 gold badges23 silver badges45 bronze badges

Collectives™ on Stack Overflow

How to construct a binary tree from level order array?

2 Answers 2

2 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

2 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related