data-structurestree

How to find level order traversal from Preorder and Inorder Traversal


Pre-order traversal of a binary tree is {8, 5, 9, 7, 1, 12, 4, 11, 3} and its in-order is {9, 5, 1, 7, 12, 8, 4, 3, 11}. A binary tree is constructed with it and level order traversal is performed. Then finally a Binary Search Tree (BST) is constructed taking the key values one at time as they appeared in the above level order traversal from left to right. What will be the level order traversal of this BST?


Solution

  • Here is my solution:

    1. Build the Tree from Inorder and PreOrder traversal.

    2. Iterate over the tree and find level order traversal (aka BFS traversal).

    public class PreAndInOrderToLevelOrderTraversal {
        static class Node {
            int val;
            Node left;
            Node right;
            public Node(int val) {
                this.val = val;
                left = null;
                right = null;
            }
        }
    
        static int[] pre;
        static int[] in;
        static ConcurrentHashMap<Integer, Integer> map;
        static Node treeRoot;
        static int preIndex = 0;
    
        public static void main(String[] args) {
            map = new ConcurrentHashMap<>();
            pre = new int[]{1, 2, 4, 5, 3};
            in = new int[]{4, 2, 5, 1, 3};
    
            treeRoot = buildTreeFromPreorderAndInOrder(pre, in, map);
            System.out.println(treeRoot.val);
            printLevelOrder();
        }
    
        public static void printLevelOrder() {
            Queue<Node> queue = new LinkedList<Node>();
            queue.add(treeRoot);
            while (!queue.isEmpty()) {
    
                /* poll() removes the present head.
                For more information on poll() visit
                http://www.tutorialspoint.com/java/util/linkedlist_poll.htm */
                Node tempNode = queue.poll();
                System.out.print(tempNode.val + " ");
    
                /*Enqueue left child */
                if (tempNode.left != null) {
                    queue.add(tempNode.left);
                }
    
                /*Enqueue right child */
                if (tempNode.right != null) {
                    queue.add(tempNode.right);
                }
            }
    
        }
    
        private static Node buildTreeFromPreorderAndInOrder(int[] pre, int[] in, ConcurrentHashMap<Integer, Integer> map) {
            // location of the item in the inorder traversal to find it quick in O(1)
            for (int i = 0; i < in.length; i++) {
                map.put(in[i], i);
            }
            return helper(in, pre, 0, pre.length - 1, map);
        }
    
        private static Node helper(int[] in, int[] pre, int inStart, int inEnd, ConcurrentHashMap<Integer, Integer> map) {
            if (inStart > inEnd) return null;
            int curr = pre[preIndex++];
            Node tNode = new Node(curr);
            if (inStart == inEnd) return tNode;
            int inIndex = map.get(curr);
            tNode.left = helper(in, pre, inStart, inIndex - 1, map);
            tNode.right = helper(in, pre, inIndex + 1, inEnd, map);
            return tNode;
        }
    }