Create binary tree from level order input

Question

I know this question might be trivial in its own way , but i am trying to generate a binary tree from level order input and then traverse through it to represent that the tree was saved in the data structure. Say if the input is like - [a,s,e,r,t,*,w] , it will generate a binary a binary tree of following representation -

Is there a way to implement this , its like generating a binary tree from a tree input. If anybody have already faced this kind of problem before , please share some sort of implementation in JAVA , Like using Queues.

How would you know what nodes belong into each level? some kind of separator would be needed. Or is the tree guaranteed to be complete? It'd be like doing the inverse of a BFS search, creating the tree from a list instead of traversing it — Óscar López
– Óscar López, Commented Aug 31, 2014 at 20:01
Thats the assumption that the provided String/List is already in the level order grammar , so the first element of String/List is root , next two are left and right respectively and so on. — NewBee
– NewBee, Commented Aug 31, 2014 at 20:04
Yes, but what if one subtree doesn't have all of its children? — Óscar López
– Óscar López, Commented Aug 31, 2014 at 20:05
Representation of such node will be represented by ''. For example if i have - [a,b,c,*,*,w,e] . This String/List states that node 'b' does not have and child nodes to it. — NewBee
– NewBee, Commented Aug 31, 2014 at 20:10

sukunrt · Accepted Answer · 2014-08-31 23:02:33Z

1

This is a rough idea but you can know exactly the range that falls on the given level.

Suppose the current level contains x non* elements from i to i+k then the next level will contain 2x elements from i+k+1 to i+k+2x, now take two pointers one on i and another on i+k+1 and assign two children to each non * element on the current level from left to right.

Similarly for the next level count how many elements the level contains that is number of non * elements. and repeat.

edited Aug 31, 2014 at 23:02

answered Aug 31, 2014 at 21:20

sukunrt

1,54310 silver badges20 bronze badges

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

Comments

stuparm · Accepted Answer · 2022-10-16 22:50:26Z

The input you provided is actually the tree represented as array. It is a common way to represent it in coding problems in leetcode etc...

In any case, you don't need the queue to generate the tree as a data structure. You would need queue to print out the generated tree.

Rules for generation the tree are quite simple:

root:  i       // array index
left:  2*i+1
right: 2*i+2

Or visually:

                    left child
                    of root
                      │ 
                      │    right child
                      │    of root
                      │     │
                      ⍒     ⍒
array values:  ┌ 3,   9,   20, null, null,   15,   7 ┐
               │ ----------------------------------- │
array indices: └ 0,   1,    2,    3,    4,    5,   6 ┘
                 ⍋
                 │
                root 


Tree representation of defined array, where values in brackets are array indices:
           3(0)
       ┌───┴───┐
    (1)9      20(2)
             ┌─┴─┐
         (5)15   7(6)

The implementation that can give you the desired tree generation can be found at: https://github.com/stuparmihailo/algo2prepare

Later, the method call is like:

TreeNode root = Tree.ints(TreeNode.class, "[3,9,20,null,null,15,7]");
Tree.print(root);
//           3
//       ┌───┴───┐
//       9      20
//             ┌─┴─┐
//            15   7

Note that I use null instead of *, but I believe that you can easily replace it in the code.

Collectives™ on Stack Overflow

Create binary tree from level order input

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related