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<Integer> preOrder = new ArrayList<Integer>();
    static List<Integer> inOrder = new ArrayList<Integer>();
    static List<Integer> postOrder = new ArrayList<Integer>();

    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<Integer> treeList) {
        List<Integer> leftSubTree = new ArrayList<Integer>();
        List<Integer> rightSubTree = new ArrayList<Integer>();

        Iterator<Integer> it = treeList.iterator();

        int rootNodeVal = root.getValue();

        while (it.hasNext()) {
            int nodeVal = it.next();
            if (rootNodeVal > nodeVal) {
                leftSubTree.add(nodeVal);
            } else if (rootNodeVal < nodeVal) {
                rightSubTree.add(nodeVal);
            }
        }

        if (leftSubTree.size() <= 3) {
            Node left = formNode(leftSubTree);
            root.setLeftNode(left);
        } else {
            formSubTrees(leftSubTree);
        }

        if (rightSubTree.size() <= 3) {
            Node right = formNode(rightSubTree);
            root.setRightNode(right);
        } else {
            formSubTrees(rightSubTree);
        }
        if (traversalType.equals(TraversalType.PREORDER)) {
            System.out.println("PRE ORDER :: " + root);
        } else if (traversalType.equals(TraversalType.INORDER)) {
            System.out.println("In ORDER :: " + root);
        } else if (traversalType.equals(TraversalType.POSTORDER)) {
            System.out.println("POST ORDER :: " + root);
        }

    }

    static Node formNode(List<Integer> 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<Integer> 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.