> 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-tree.md).

# Binary Tree

[Binary Tree](https://en.wikipedia.org/wiki/Binary_tree) is a data structure to store hierarchical data where each node has only two leaf nodes.

## Binary Tree using Nodes

The basic building block of binary tree is a node that hold references to left and right nodes.

```
class TreeNode<T> {
    T value;
    TreeNode left;
    TreeNode right;

    public TreeNode(T value) {
        this.value = value;
    }
}
```

Then we create a class that holds the root and provide operations over the binary tree.

```
class BinaryTree<T> {
    TreeNode<T> root;

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

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

Now we can try to use it and print out how the tree looks like.

```
public class BinaryTreeDemo {

    public static void main(String... args) {
        BinaryTree<String> tree = new BinaryTree<>();
        tree.root = new TreeNode<>("Hello");
        tree.root.left = new TreeNode<>("World");
        tree.root.right = new TreeNode<>("!!!");

        System.out.println(tree);
    }
}
```

Here is the output.

```
0: Hello
1: World
1: !!!
```

## Binary Tree using Array

An alternative to represent trees using node is to keep the values in array. Root element is stored on `0th` position, left is stored on `0th + 1` position and right is stored on `0th + 2` position. If a position of element is i, then left is on `2*i+1` and right is on `2*i+2`. For 0th element, it is `0*2+1` and `0*2+2`. For the left element on `0th` position, it is `2*1+1` and `2*1+2`.

![](/files/-M3wYlUqjje0YI8gK5Sc)

Here is an implementation of binary tree that stores and obtains elements from binary tree.

```
class BinaryTreeUsingArray {
    private String[] values;

    BinaryTreeUsingArray() {
        values = new String[10];
    }

    public void setRoot(String value) {
        values[0] = value;
    }

    public void addLeftChild(String value, int root) {
        values[2 * root + 1] = value;
    }

    public void addRightChild(String value, int root) {
        values[2 * root + 2] = value;
    }

    public String toString() {
        return Arrays.toString(values);
    }

    public String asTree() {
        StringBuilder builder = new StringBuilder();
        int stop = 1;
        for (int i = 0; i < values.length; i++) {
            if (values[i] == null) continue;
            if (i < stop - 1) {
                builder.append(values[i]);
                builder.append(" ");
            } else {
                builder.append("\n");
                builder.append(values[i]);
                builder.append(" ");
                stop = stop << 1; // 1, 2, 4, 8, 16, 32 ...
            }
        }
        return builder.toString();
    }
}
```

Here is the output.

```
public class BinaryTreeDemo {

    public static void main(String... args) {
        BinaryTreeUsingArray t = new BinaryTreeUsingArray();
        t.setRoot("A");
        t.addLeftChild("B", 0);
        t.addRightChild("C", 0);
        t.addLeftChild("D", 1);
        t.addRightChild("E", 1);
        t.addLeftChild("F", 2);
        t.addRightChild("G", 2);

        System.out.println(t);
        System.out.println(t.asTree());
    }
}
```

Here is the output.

```
[A, B, C, D, E, F, G, null, null, null]

A 
B C 
D E F G
```

## Balanced & Unbalanced Trees

A balanced binary tree has the minimum possible maximum height (a.k.a. depth).

```
 h      Balanced      Unbalanced, h = (n + 1)/2 - 1
 0:      ABCDE               ABCDE
        /     \             /     \
 1:    ABCD   E             ABCD   E
      /    \               /    \
 2:  AB    CD             ABC     D
    /  \  /  \           /   \
 3: A  B  C  D          AB   C
                       /  \
 4:                   A   B
```


---

# 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-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.