Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

• The left sub-tree of a node has a key less than or equal to its parent node's key.
• The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Copied from here.

My Solution:

public class Node {

Node left, right;

int value;

public Node(int value) {

this.value = value;

}

public Node add(int value) {

if (value < this.value)

if (this.left != null)

return this.left.add(value);

else

return this.left = new Node(value);

if (value > this.value)

if (this.right != null)

return this.right.add(value);

else

return this.right = new Node(value);

return this;

}

public Node find(int v) {

if (this == null || v == value)

return this;

else if (value > v && this.left != null)

return left.find(v);

else if (value < v && this.right != null)

return right.find(v);

else

return null;

}

public int findSmallestValue() {

return this.left == null ? this.value : this.left.findSmallestValue();

}

public void traverseInOrder() {

if (this.left != null)

this.left.traverseInOrder();

System.out.print(" " + this.value);

if (this.right != null)

this.right.traverseInOrder();

}

public void traversePreOrder() {

System.out.print(" " + this.value);

if (this.left != null)

this.left.traversePreOrder();

if (this.right != null)

this.right.traversePreOrder();

}

public void traversePostOrder() {

if (this.left != null)

this.left.traversePostOrder();

if (this.right != null)

this.right.traversePostOrder();

System.out.print(" " + this.value);

}

}