Building a binary tree from pre-order

Question

This is an interview question with Amazon. Can anyone give an algorithm for this?

There is a binary tree with the following properties:

• All its internal nodes have a value of 'N' , and all leaves have a value of 'L' .
• Each node has two children or no child.

Given its pre-order, build a tree and return the root of the node.

Answer 1

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 2

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

We call our function with the input provided, and it checks the first character that it received. If it is a leaf node, it just returns the leaf. If it is an internal node, it simply calls itself for the left and right subtrees and returns the tree formed with node as root, and the left and right subtrees as its left and right child elements.

The following is the code (in Python). Please note: I am using tuple to represent node, therefore the tree is tuple 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: Java code

 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 3

I can think of a recursive algorithm.

head = new node. delete first character in preorderString
Call f(head, preorderString)

Recursive function f(node, s)
- first remove the char with s, if L , then attach to the node as a leaf.
otherwise create nodeLeft, join node, call f (nodeLeft, s)
- first remove the char with s, if L , then attach to the node as a leaf.
otherwise create nodeRight, join node, call f (nodeRight, s)

Answer 4

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

• NN: the second N is the left child of the first N, but we do not know that the right child of the first N
• NL ?: the second N is the left child of the first N, and the right child of the first N is?
• L?:? is the right child STACK top

STACK is used because when we read a node in a pre-order sequence, we don’t know where its right child is (we know where its left child is, if any). STACK stores this node, so when its right child appears, we can pop it up and terminate its correct 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 above code has been tested using some simple cases. Hope this is correct.