CODEWITHSUNDEEP
javaalgorithmtreequeuebinary-tree
NewBee
NewBee

Reputation: 839

Create binary tree from level order input

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 -

                    a
                   / \
                  s   e
                 /\   /\
                r  t *  w

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.

Upvotes: 0

Views: 774

Answers (2)

stuparm
stuparm

Reputation: 553

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.

Upvotes: 0

sukunrt
sukunrt

Reputation: 1543

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.

Upvotes: 1

Related Questions