Expedia Interview Question: post order traversal of a Bin... | Glassdoor

Interview Question

Software Development Engineer In Test (SDET) II Interview Bellevue, WA

post order traversal of a Binary Search Tree Follow up

  Create a BST from this post order traversed array and write test cases for this function
Answer

Interview Answer

3 Answers

0

Creating a BST from the post order traversal output would involve adding the nodes in reverse order of the post order traversal output. For example, if the post order traversal output was 2,4,3,20. I would insert in the following order: 20, 3, 4, 2. Can anyone confirm if this is correct?

RG on Mar 20, 2013
0

package test;

import java.util.ArrayList;
import java.util.List;

public class TreeTraversal {
    static List preOrder = new ArrayList();
    static List inOrder = new ArrayList();
    static List postOrder = new ArrayList();

    static void traverseTree(Node root) {
        Node left = root.getLeftNode();
        Node right = root.getRightNode();

        if (null == left.getLeftNode()
                && null == left.getRightNode()
                && null == right.getLeftNode()
                && null == right.getRightNode()) {
            preOrder.add(root.getValue());
            preOrder.add(left.getValue());
            preOrder.add(right.getValue());

            inOrder.add(left.getValue());
            inOrder.add(root.getValue());
            inOrder.add(right.getValue());

            postOrder.add(left.getValue());
            postOrder.add(right.getValue());
            postOrder.add(root.getValue());
        } else {
            preOrder.add(root.getValue());
            traverseTree(left);
            inOrder.add(root.getValue());
            traverseTree(right);
            postOrder.add(root.getValue());
        }
    }

    public static void main(String[] args) {
        Node left = new Node(2, new Node(1), new Node(3));
        Node right = new Node(6, new Node(5), new Node(7));
        Node root = new Node(4, left, right, true);
        traverseTree(root);
        System.out.print("Pre Order Traversal ::");
        System.out.println(preOrder);
        System.out.print("In Order Traversal ::");
        System.out.println(inOrder);
        System.out.print("Post Order Traversal ::");
        System.out.println(postOrder);

    }
}

Pur Tree Traversal on Aug 14, 2013
0

package test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

enum TraversalType {
    PREORDER, INORDER, POSTORDER;
}

public class ConstructTreeBack {
    static Node root = new Node();
    static TraversalType traversalType;

    static void formSubTrees(List treeList) {
        List leftSubTree = new ArrayList();
        List rightSubTree = new ArrayList();

        Iterator it = treeList.iterator();

        int rootNodeVal = root.getValue();

        while (it.hasNext()) {
            int nodeVal = it.next();
            if (rootNodeVal > nodeVal) {
                leftSubTree.add(nodeVal);
            } else if (rootNodeVal treeList) {
        Node node = new Node();
        if (traversalType.equals(TraversalType.PREORDER)) {
            if (null != treeList.get(0)) {
                node.setValue(treeList.get(0));
            }
            if (null != treeList.get(1)) {
                node.setLeftNode(new Node(treeList.get(1)));
            }
            if (null != treeList.get(2)) {
                node.setRightNode(new Node(treeList.get(2)));
            }
        } else if (traversalType.equals(TraversalType.INORDER)) {
            if (null != treeList.get(1)) {
                node.setValue(treeList.get(1));
            }
            if (null != treeList.get(0)) {
                node.setLeftNode(new Node(treeList.get(0)));
            }
            if (null != treeList.get(2)) {
                node.setRightNode(new Node(treeList.get(2)));
            }
        } else if (traversalType.equals(TraversalType.POSTORDER)) {
            if (null != treeList.get(2)) {
                node.setValue(treeList.get(2));
            }
            if (null != treeList.get(0)) {
                node.setLeftNode(new Node(treeList.get(0)));
            }
            if (null != treeList.get(1)) {
                node.setRightNode(new Node(treeList.get(1)));
            }
        }
        return node;
    }

    public static void main(String[] args) {

        int rootNodeVal = 0;
        List treeList;

        /*PRE ORDER TRAVERSAL*/
        Integer treeArrPreOrder[] = { 4, 2, 1, 3, 6, 5, 7 };

        rootNodeVal = treeArrPreOrder[0]; root.setValue(rootNodeVal);
        root.setRoot(true);

        treeList = Arrays.asList(treeArrPreOrder);
        traversalType = TraversalType.PREORDER;
        formSubTrees(treeList);

        /*IN ORDER TRAVERSAL*/
        Integer treeArrInOrder[] = { 1, 2, 3, 4, 5, 6, 7 };

        int rootIndex = 3;
        root.setValue(treeArrInOrder[rootIndex]);
        root.setRoot(true);

        treeList = Arrays.asList(treeArrInOrder);
        traversalType = TraversalType.INORDER;
        formSubTrees(treeList);

        /*POST ORDER TRAVERSAL*/
        Integer treeArrPostOrder[] = { 1, 3, 2, 5, 7, 6, 4 };

        rootNodeVal = treeArrPostOrder[treeArrPostOrder.length - 1];
        root.setValue(rootNodeVal); root.setRoot(true);

        treeList = Arrays.asList(treeArrPostOrder);
        traversalType = TraversalType.POSTORDER;
        formSubTrees(treeList);

    }
}

Pur reconstruct tree on Aug 14, 2013

Add Answers or Comments

To comment on this, Sign In or Sign Up.