> For the complete documentation index, see [llms.txt](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/binary-search-tree.md).

# Binary Search Tree

[Binary Search Tree](https://en.wikipedia.org/wiki/Binary_search_tree) is a data structure to store hierarchical data where each node has only two leaf nodes and nodes are sorted from left to right. BST is also called ordered or sorted binary tree.

A Binary Search Tree is a special form of a binary tree. The value in each node must be greater than (or equal to) any values in its left subtree but less than (or equal to) any values in its right subtree.

Like a normal binary tree, we can traverse a BST in preorder, inorder, postorder or level-order. However, it is noteworthy that inorder traversal in BST will be in ascending order. Therefore, the inorder traversal is the most frequent used traversal method of a BST.

BST is good for searching in general `O(log n)`. Heaps are the best when we want to get maximum or minimum of set of values, complexity of `O(1)`. More about the difference between [heap and BST](https://cs.stackexchange.com/questions/27860/whats-the-difference-between-a-binary-search-tree-and-a-binary-heap).

The basic algorithm is: when we want to put a value into the tree, we go from the root and we put smaller values on left and higher values on right side.

```
import java.util.LinkedList;
import java.util.Queue;

class BinarySearchTree<T extends Comparable<T>> {

    TreeNode<T> root;

    public void add(T value) {
        if (root == null) {
            root = new TreeNode<>(value);
        } else {
            addNode(value, root);
        }
    }

    public void addNode(T value, TreeNode<T> node) {
        if (isValueHigherThanNodeValue(value, node)) {
            // higher values go on left
            addToRight(value, node);
        } else {
            // lower values go on left
            addToLeft(value, node);
        }
    }

    private void addToLeft(T value, TreeNode<T> node) {
        if (node.left == null) {
            node.left = new TreeNode<>(value);
            return;
        }
        addNode(value, node.left);
    }

    private void addToRight(T value, TreeNode<T> node) {
        if (node.right == null) {
            node.right = new TreeNode<>(value);
            return;
        }
        addNode(value, node.right);
    }

    private boolean isValueHigherThanNodeValue(T value, TreeNode<T> current) {
        return value.compareTo(current.value) > 0;
    }

    public String toString() {
        return asString(root, 0);
    }

    private String asString(TreeNode<T> node, int level) {
        if (node == null) return null;
        String result = spaces(level) + node.value.toString() + " \n";
        level++;
        if (node.left != null) {
            result += asString(node.left, level);
        }
        if (node.right != null) {
            result += asString(node.right, level);
        }
        return result;
    }

    private String spaces(int level) {
        String spaces = "";
        for (int i = 0; i < level; i++) {
            spaces += "-";
        }
        return spaces;
    }

    // read to queue in 'breath first' order
    public Queue<TreeNode<T>> readToQueue(TreeNode<T> node) {
        Queue<TreeNode<T>> queue = new LinkedList<>();
        Queue<TreeNode<T>> temp = new LinkedList<>();
        temp.add(node);
        while (temp.size() > 0) {
            TreeNode<T> n = temp.poll();
            queue.add(n);
            if (n.left != null) {
                temp.add(n.left);
            }
            if (n.right != null) {
                temp.add(n.right);
            }
        }
        return queue;
    }

    // breath first or a.k.a. level order traversal
    // -> A
    // -> B -> C
    // -> D -> E -> F -> G
    public String breathFirst(TreeNode<T> node) {
        Queue<TreeNode<T>> queue = new LinkedList<>();
        queue.add(node);
        String value = "";
        while (queue.size() > 0) {
            TreeNode<T> n = queue.poll();
            value += n.value.toString() + " ";
            if (n.left != null) {
                queue.add(n.left);
            }
            if (n.right != null) {
                queue.add(n.right);
            }
        }
        return value;
    }

    enum Order {
        Pre, In, Post
    }

    // pre order traversal - root, left, right
    // in order traversal - left, root, right
    // post order traversal - left, right root
    public String depthFirst(TreeNode<T> node, Order order) {
        if (node == null) return null;
        String value = "";
        if (order.equals(Order.Pre)) {
            value += node.value.toString() + " ";
        }
        if (node.left != null) {
            value += depthFirst(node.left, order);
        }
        if (order.equals(Order.In)) {
            value += node.value.toString() + " ";
        }
        if (node.right != null) {
            value += depthFirst(node.right, order);
        }
        if (order.equals(Order.Post)) {
            value += node.value.toString() + " ";
        }

        return value;
    }
}
```

We have implemented few types of tree traversal. Here is code that creates BST and uses couple of BST traversals.

```
import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTreeDemo {
    public static void main(String... args) {
        BinarySearchTree<Integer> bst = new BinarySearchTree<>();

        bst.add(10);
        bst.add(5);
        bst.add(15);
        bst.add(2);
        bst.add(0);
        bst.add(25);
        bst.add(20);

        System.out.println("BST:");
        System.out.println(bst);

        System.out.println("Breath First:");
        System.out.println(bst.breathFirst(bst.root));

        System.out.println("Pre order:");
        String preOrder = bst.depthFirst(bst.root, BinarySearchTree.Order.Pre);
        System.out.println(preOrder);

        System.out.println("In order:");
        String inOrder = bst.depthFirst(bst.root, BinarySearchTree.Order.In);
        System.out.println(inOrder);

        System.out.println("Post order:");
        String postOrder = bst.depthFirst(bst.root, BinarySearchTree.Order.Post);
        System.out.println(postOrder);
    }
}
```

Here is the output.

```
BST:
10 
-5 
--2 
---0 
-15 
--25 
---20 

Breath First:
10 5 15 2 25 0 20 
Pre order:
10 5 2 0 15 25 20 
In order:
0 2 5 10 15 20 25 
Post order:
0 2 5 20 25 15 10
```


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://ondrej-kvasnovsky-2.gitbook.io/algorithms/data-structures/binary-search-tree.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.