Google Interview Question: 1. Given a binary tree and in... | Glassdoor.com.au

Interview Question

Software Engineer Interview(Student Candidate)

1. Given a binary tree and inorder traversal, construct a

  new binary tree with additional pointers such that the inorder traversal is reflected in the new tree
Tags:
algorithm
Answer

Interview Answer

1 Answer

0

The description of the problem is a little bit vague (what does 'reflected' mean?) but I am going to take it as a question of creating a threaded binary tree in disguise.

So given a BST, we want to make it threaded, that is, we want to be able to traverse it in order with constant memory overhead O(1), that is, no auxiliary stack object or recursive calls in the system stack.

The idea is that we traverse the BST in order the first time using iteration (can be done with recursion too) and whenever we pop something out of the stack, we check to see if its right child is null. If it is not, then the right child is the in order successor. But if it is null, then the in order successor will be the next element in the stack, which we will peek, not pop.

We also need to keep track of each node's parent during the creation of the threaded tree. We also need to modify the tree so that every node can hold a binary flag if it points to a thread or not.

The code to built a threaded BST given a BST is as follows:

public void makeThreaded(BST.Node root){

        if(root==null) return;
        Stack stack = new Stack();
        BST.Node current = root, parent = root;

        while(true){

            if(current!=null){

                    stack.push(current);
                    parent = current;
                    current = current.leftChild;

            }

            else{

                if(stack.empty()) break;

                current = stack.pop();

                System.out.println(current.key); //this symbolizes the inorder action, here it justs prints

                parent = current;
                current = current.rightChild;

                if(current==null) {
                                           parent.threaded = true;
                                           if(stack.empty()) parent.rightChild = null;
                                           else parent.rightChild = stack.peek();
                                 }
            }
        }
    }

Anonymous on 4 Jan 2015

Add Answers or Comments

To comment on this, Sign In or Sign Up.