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

Question

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

RG · Accepted Answer

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?

Pur Tree Traversal · Answer

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 reconstruct tree · Answer

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);
		
	}
}

Expedia Group

Pergunta de entrevista da empresa Expedia Group

Respostas da entrevista

Empresas seguidas

Buscas de vagas