Construct a perfect Binary Tree from a depth first search output

Question

Assume you have a perfect binary tree, something like this

         0
     /        \
    1           2      
   / \         / \
  3    4       5   6
 / \  / \    / \   / \
7  8 9  10 11  12 13 14

Given its depth and output of node values as a depth first search array, eg.

Depth: [4]

Dfs Array: [0,1,3,7,8,4,9,10,2,5,11,12,6,13,14]

write code that returns it as a Binary Tree. How would you do it(recursive/non-recursive)?

I am not sure if it is possible to solve this recursively since I don't have info about which nodes are leaves Vs non leaves. Having that information allows one to construct the tree recursively. Without recursion, I was trying to do something like this, but I am getting stuck on getting this all the way.

TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
    }
}

TreeNode makeTree(int[] dfs, int depth) {
    TreeNode root = new TreeNode(dfs[0]);
    Deque<TreeNode> dq = new LinkedList<>();
    dq.addFirst(root);

    while (!dq.isEmpty()) {
        int i;
        for (i = 1; i < depth - 1; i++) {
           TreeNode t = dq.getFirst();
           t.left = new TreeNode(dfs[i]);
           dq.addFirst(t.left);
    }
    TreeNode t = dq.getFirst();
    t.left = new TreeNode(dfs[i++]);
    dq.addFirst(t.left);
    t.right = new TreeNode(dfs[i++)];
    dq.addFirst(t.right);
   }
   // More code here to construct the tree?
   .........
   // return the root
   return dq.getLast();
}

To expect answers, you need to show that you've made a couple of attempts to answer the question yourself, and explain why you think your attempts didn't work out. — lefft

c0der c0der · Accepted Answer · 2018-02-16T14:05:21

The following code builds a binary tree from the array representing dfs results.
Note the comments and do not hesitate to ask were they are not sufficient:

public class GraphFromDfs{

    public static void main(String[] args) {

        int[] dfsArray = new int[]{0,1,3,7,8,4,9,10,2,5,11,12,6,13,14};
        TreeNode root = makeTree(dfsArray, 4);
        printTreeFromRoot(root);
    }

    private static TreeNode makeTree(int[] dfsArray, int depth) {

        //array to store all nodes
        TreeNode[] nodes = new TreeNode[dfsArray.length];

        //create all nodes from int[] array
        for(int i=0; i< dfsArray.length; i++) {
            nodes[i]= new TreeNode(dfsArray[i]); //nodes stored in the same order as int array
        }

        makeTree(nodes, depth);
        return nodes[0] ;
    }

    //process nodes to add links (create a tree)
    private static void makeTree(TreeNode[] nodes, int depth) {

        int currentDepth = 0;
        int index = 0; //index of node in nodes array
        TreeNode root = nodes[0];
        //stack all nodes to be processed. add root as first
        LinkedList<TreeNode> stack = new LinkedList<>();
        stack.add(root);

        while (! stack.isEmpty()) {

            TreeNode node = stack.peekLast();

            if(node.left == null) { node.left = nodes[++index]; }         //process left or right if
            else if (node.right == null) { node.right = nodes[++index]; } //any is null. update index

            //add next node to stack to be processed if not a leaf.
            //leaf does not need to be processed
            if((currentDepth +2) < depth ) {

                stack.add(nodes[index]);
                currentDepth++;

            //if leaf - backtrack. move up the tree
            //note that this is in line with "perfect binary tree" as asked
            }else if((node.right != null) && (node.left != null)) {

                while (! stack.isEmpty()) {
                    TreeNode n = stack.peekLast();
                    if((n.left != null) && (n.right != null)) {
                        stack.remove(n); //remove fully processed nodes
                                         //(right and left are not null)
                        currentDepth --; //backtrack
                    }else {
                        break;
                    }
                }
            }
        }
    }

    private static void printTreeFromRoot(TreeNode root) {

        if(root == null) { return;}
        System.out.println("--------- TREE  ---------");
        System.out.println( root);
        printTree(root);
        System.out.println("--------------------------");
    }

    //recursive tree print
    private static void printTree(TreeNode root) {

        if(root.left != null ) {
            System.out.println( root.left);
            printTree(root.left);
        }
        if(root.right != null ) {
            System.out.println( root.right);
            printTree(root.right);
        }
    }
}

class TreeNode {

    int value;
    TreeNode left, right;

    TreeNode(int value) {
        this.value = value;
    }

    @Override
    public String toString() {

        StringBuilder s = new StringBuilder("N:"+ value);
        s.append( left == null ? " L-null" : " L-"+left.value);
        s.append( right == null ? " R-null" : " R-"+right.value);
        return s.toString();
    }
}

Output

Construct a perfect Binary Tree from a depth first search output

1 Answers