 ## JAVA EXAMPLE PROGRAMS

Publish Your Article Here

# Program: Implement Binary Search Tree (BST) post-order traversal (depth first).

Description:

For a binary tree to be a binary search tree (BST), the data of all the nodes in the left sub-tree of the root node should be less than or equals to the data of the root. The data of all the nodes in the right subtree of the root node should be greater than the data of the root. This example shows the implementation of a binary search tree post-order traversal (depth first).

### What is post-order traversal (depth first)?

Tree traversal means we visiting all nodes in the tree, visiting means either of accessing node data or processing node data. Traversal can be specified by the order of visiting 3 nodes, ie current node, left subtree and right subtree. In post-order traversal, first we visit the left subtree, then the right subtree, and then current node. In our current example we use recursive approach to implement post-order traversal. Post-order: A, C, E, D, B, H, I, G, F.

Here is an example picture of binary search tree (BST) for our example code: Here is the steps to implement post-order traversal:

1. Start with root node.
2. Check if the current node is empty / null.
3. Traverse the left subtree by recursively calling the post-order function.
4. Traverse the right subtree by recursively calling the post-order function.
5. Display the data part of the root (or current node).

 BstNode ```package com.java2novice.ds; public class BstNode { private BstNode left; private BstNode right; private Integer data; public BstNode(Integer data) { this.data = data; } public BstNode getLeft() { return left; } public void setLeft(BstNode left) { this.left = left; } public BstNode getRight() { return right; } public void setRight(BstNode right) { this.right = right; } public Integer getData() { return data; } } ```

 BinarySearchTreeImpl ```package com.java2novice.ds; import java.util.LinkedList; import java.util.Queue; public class BinarySearchTreeImpl { private BstNode root; public boolean isEmpty() { return (this.root == null); } public void insert(Integer data) { System.out.print("[input: "+data+"]"); if(root == null) { this.root = new BstNode(data); System.out.println(" -> inserted: "+data); return; } insertNode(this.root, data); System.out.print(" -> inserted: "+data); System.out.println(); } private BstNode insertNode(BstNode root, Integer data) { BstNode tmpNode = null; System.out.print(" ->"+root.getData()); if(root.getData() >= data) { System.out.print(" [L]"); if(root.getLeft() == null) { root.setLeft(new BstNode(data)); return root.getLeft(); } else { tmpNode = root.getLeft(); } } else { System.out.print(" [R]"); if(root.getRight() == null) { root.setRight(new BstNode(data)); return root.getRight(); } else { tmpNode = root.getRight(); } } return insertNode(tmpNode, data); } public void postOrderTraversal() { doPostOrder(this.root); } private void doPostOrder(BstNode root) { if(root == null) return; doPostOrder(root.getLeft()); doPostOrder(root.getRight()); System.out.print(root.getData()+" "); } public static void main(String a[]) { BinarySearchTreeImpl bst = new BinarySearchTreeImpl(); bst.insert(8); bst.insert(10); bst.insert(14); bst.insert(3); bst.insert(6); bst.insert(7); bst.insert(1); bst.insert(4); bst.insert(13); System.out.println("\n-------------------"); System.out.println("Post Order Traversal"); bst.postOrderTraversal(); } } ```

 Output: ```[input: 8] -> inserted: 8 [input: 10] ->8 [R] -> inserted: 10 [input: 14] ->8 [R] ->10 [R] -> inserted: 14 [input: 3] ->8 [L] -> inserted: 3 [input: 6] ->8 [L] ->3 [R] -> inserted: 6 [input: 7] ->8 [L] ->3 [R] ->6 [R] -> inserted: 7 [input: 1] ->8 [L] ->3 [L] -> inserted: 1 [input: 4] ->8 [L] ->3 [R] ->6 [L] -> inserted: 4 [input: 13] ->8 [R] ->10 [R] ->14 [L] -> inserted: 13 ------------------- Post Order Traversal 1 4 7 6 3 13 14 10 8 ```

#### List Of All Interview Programs:

Java2Novice - YouTube Channel
Knowledge Centre
Transient and Volatile Modifiers
Transient: The transient modifier applies to variables only and it is not stored as part of its object's Persistent state. Transient variables are not serialized.

Volatile: Volatile modifier applies to variables only and it tells the compiler that the variable modified by volatile can be changed unexpectedly by other parts of the program.
Famous Quotations
There is a great difference between worry and concern. A worried person sees a problem, and a concerned person solves a problem.
-- Harold Stephens

### Other Interesting Sites

 Reference: Java™ Platform Standard Ed. 7 - API Specification | Java™ Platform Standard Ed. 8 - API Specification | Java is registered trademark of Oracle. Privacy Policy | Copyright © 2019 by Nataraja Gootooru. All Rights Reserved.