The Binary Search Tree (BST)

First, before defining what a tree is, let us explore the motivation behind why and when we should it use it. For the linear data structures such as Array of size $n$ and linked list of size $n$, we have problems, namely in the time complexities when we want to perform operations:

For an array or a linked list of size $n$:

• An insertion is $O(1)$
• Searching is $O(n)$
• Deletion is $O(n)$

For a sorted array of size $n$:

• Searching is $O(\log n)$
• An insertion is $O(n)$
• Deletion is $O(n)$

On the other hand, as we will see, Trees (that are balanced) will neatly combine the advantages of both data structures.

What is a Tree?

A tree is a data structure that consists of nodes and edges with hierarchical relationships (parent-child). Each node consists of stored data, and of pointers to the children of that node.

Let’s take a look at the properties of a tree:

• It has a hierarchical structure.
• Each node $n$ except the root has a single parent.
• Each node stores a value.
• A leaf is a node without any children.
• Nodes are connected by edges (lines)

The idea here is that each node distributes the values to its descendants in an orderly manner. This will provide us an efficient way of navigating from the root to the leaf that contains the element, of which it’s key is closest to that we’re looking for.

What is a Binary Tree?

A binary tree is a form of a tree data structure, in which each node has at most two children, referred to as the left child and the right child.

A node in a binary tree has the following properties:

• Depth - The depth of a node in a binary tree is the number of edges in the unique path from the root node to that specific node.
• Height - The height of a node in a tree is defined as the number of edges on the longest downward path from that specific node to a leaf node.