binary tree construction from preorder

Question

This is an Amazon interview question. Can any one give an algorithm to do this?

There is a binary tree with the following properties:

• All of its inner node have the value 'N', and all the leaves have the value 'L'.
• Every node either has two children or has no child.

Given its preorder, construct the tree and return the root node.

Answer 1

Since it is guaranteed that each internal node has exactly 2 children, we can simply build the tree recursively using that.

We call our function with the input provided, and it examines the first character it got. If it is a leaf node, it just returns a leaf. If it is an internal node, it just calls itself for the left and right subtrees and returns the tree formed using the node as root and the left and right subtrees as its left and right children.

Code follows (in Python). Note, I am using tuples to represent node, so the tree is a tuple of tuples.

#! /usr/bin/env python
from collections import deque

def build_tree(pre_order):
        root=pre_order.popleft()
        if root=='L':
                return root
        else:
                return (root,build_tree(pre_order),build_tree(pre_order))

if __name__=='__main__':
        print build_tree(deque("NNLLL"))

Edit: Code in Java

import java.util.*;
class Preorder{
        public static Node buildTree(List<Character> preorder){
                char token=preorder.remove(0);
                if (token=='L'){
                        return new Node(token,null,null);
                }
                else{
                        return new Node(token,buildTree(preorder),buildTree(preorder));

                }
        }
        public static void main(String args[]){
                List<Character> tokens=new LinkedList<Character>();
                String input="NNLLL";
                for(int i=0;i<input.length();i++) tokens.add(input.charAt(i));
                System.out.println(buildTree(tokens));
        }
}

class Node{
        char value;
        Node left,right;
        public Node(char value, Node left, Node right){
                this.value=value;
                this.left=left;
                this.right=right;
        }

        public String toString(){
                if (left==null && right==null){
                        return "("+value+")";
                }
                else{
                        return "("+value+", "+left+", "+right+")";
                }
        }
}

Answer 2

I can think of a recursive algorithm.

head = new node. remove first character in preorderString
Invoke f(head, preorderString)

Recursive function f(node, s)
- remove first char from s, if L then attach to node as leaf.
else create a nodeLeft, attach to node, invoke f(nodeLeft, s)
- remove first char from s, if L then attach to node as leaf.
else create a nodeRight, attach to node, invoke f(nodeRight, s)

Answer 3

I think the key point is to realize that there are three possibilities for the adjacent nodes: NN, NL?, L? (``?'' means either N or L)

1. NN: the second N is the left child of the first N, but we don't know what the right child of the first N is
2. NL?: the second N is the left child of the first N, and the right child of the first N is ?
3. L?: ? is the right child of STACK top

A STACK is used because when we read a node in a preorder sequence, we don't know where its right child is (we do know where its left child is, as long as it has one). A STACK stores this node so that when its right child appears we can pop it up and finish its right link.

NODE * preorder2tree(void)
{
    NODE * head = next_node();
    NODE * p = head;
    NODE * q;

    while (1) {
            q = next_node();
            if (!q)
                    break;

            /* possibilities of adjacent nodes:
             * NN, NL?, L?
             */
            if (p->val == 'N') {
                    p->L = q;
                    if (q->val == 'N') { /* NN */
                            push(p);
                            p = q;
                    } else {             /* NL? */
                            q = next_node();
                            p->R = q;
                            p = q;
                    }
            } else {                     /* L? */
                    p = pop();
                    p->R = q;
                    p = q;
            }
    }
    return head;
}

The code above was tested using some simple cases. Hopefully it's correct.

Answer 4

Here is the java program::

import java.util.*;

class preorder_given_NNNLL {

static Stack<node> stk = new Stack<node>();
static node root=null;

  static class node
  {
      char value;
      node left;
     node right;
      public node(char value)
      {
              this.value=value;
              this.left=null;
              this.right=null;
      }


  }

  public static node stkoper()
  {
      node posr=null,posn=null,posl=null;
      posr=stk.pop();
      if(stk.empty())
      {
          stk.push(posr);
          return null;
      }
      else
          posl=stk.pop();

      if(stk.empty())
      {
          stk.push(posl);
          stk.push(posr);
          return null;

      }
      else
      {
          posn=stk.pop();
      }


      if( posn.value == 'N' && posl.value == 'L' && posr.value == 'L')
      {

          root = buildtree(posn, posl, posr);

          if(stk.empty())
          {
              return root;

          }
          else
          {
              stk.push(root);


              root=stkoper();
          }
      }
      else
      {
          stk.push(posn);
          stk.push(posl);
          stk.push(posr);
      }
    return root;


  }


  public static node buildtree(node posn,node posl,node posr)
  {         
      posn.left=posl;
      posn.right=posr;
      posn.value='L';
      return posn;

  }

  public static void inorder(node root)
    {
        if(root!=null)
        {
            inorder(root.left);
            if((root.left == null) && (root.right == null))
                System.out.println("L");
            else
                System.out.println("N");
            inorder(root.right);
        }
}

  public static void main(String args[]){

          String input="NNNLLLNLL";
          char[] pre = input.toCharArray();
         for (int i = 0; i < pre.length; i++) 
         {
            node temp = new node(pre[i]);
            stk.push(temp);
            root=stkoper();
         }

         inorder(root);

  }

}

Answer 5

The construct function does the actual tree construction. The code snippet is the solution for the GeeksforGeeks question that you mentioned as above.

    struct Node*construct(int &index, Node*root, int pre[], int n, char preLN[])
{   
    Node*nodeptr;
    if(index==n)
    {
        return NULL;
    }
    if(root==NULL)
    {
        nodeptr = newNode(pre[index]);
    }
    if(preLN[index]=='N')
    {   
        index = index+1;
        nodeptr->left = construct(index, nodeptr->left, pre,n,preLN);
        index = index+1;
        nodeptr->right = construct(index, nodeptr->right,pre,n,preLN);
        return nodeptr;
    }
    return nodeptr;
}
struct Node *constructTree(int n, int pre[], char preLN[])
{   
    int index =0;
    Node*root = construct(index,NULL,pre,n,preLN);
    return root;
}

Points to Note:

1. Index has been declared a reference variable so that on returning back to the parent node, the function starts constructing the tree from the overall most recent value of index and not the value of index as possessed by the function when initially executing the call.

2. Different values of index for right and left subtrees since preorder traversal follows Root, Left ,Right sequence of nodes.

Hope it Helps.