Data Structures and Algorithms (DSA) using C# .NET Core — Binary Trees and Binary Search Tree (BST)

Trees are one of the most common data structures used. A tree is a non-linear data structure that is used to store data in a hierarchical manner. In this article, we will discuss a tree and then learn about a binary tree along with an implementation of a binary tree — the Binary Search Tree, also known as BST.

What is a Tree?

A tree consists of a set of nodes or a collection of nodes connected by edges such that the nodes have a parent-child relationship. In a tree, the parent-child relationship is established through edges. The nodes and edges are linked together (in one direction) to simulate the hierarchy. An example of a tree is Fig. 1- Organizational chart.

Fig 1: Organizational Chart

Similar to the Organizational chart is the Tree structure: fig. 2

Fig. 2: Tree Structure

Some of the terminologies used in a Tree structure.

1. Each node has a value, also referred to as a key value.
2. The top node of a tree is called the Root node. If the node is connected by an edge to another node, the top node is called the parent, and the node below is called its children.
3. A pair of nodes (p,c) is connected by an edge. The edge always has the relationship between parent and child.
4. A node can have zero or more child nodes connected. (Binary Trees are special types of trees where a node can have no more than two nodes). A node without any child node is called a leaf node.
5. You can travel from one node to another node following the edge. The series of edges you follow to get from one node to another is called a path. Visiting all nodes in a tree in different orders is called tree traversal. (Pre-order, In-order, Post-order).
6. A tree is broken down into levels. The root node is called Level 0. Its children are at Level 1, those nodes children are at Level 2 and so on. We can define the depth of a tree as an equal number of layers (level) in the tree.

Remember: for n number of nodes in a tree, there will always be n-1 number of edges. All nodes except the root node will have exactly 1 incoming edge.

Question: Can a tree be empty?

Answer: Yes, a tree that does not have any nodes (children) is called an empty tree.

Types of Tree

1. Binary Tree
2. Binary Search Tree (implementation of Binary Tree)
3. B-Tree
4. AVL Tree

Binary Tree

A binary tree is defined as a tree where each node can have no more than two children (i.e. 0, 1, or at max 2 children). Fig. 3

Fig. 3: Binary Tree Structure

A binary tree has the following properties

1. Every node in a binary tree has at most two children i.e. every node has 0, 1, or 2 children. It cannot have more than two children.
2. Every child node is labeled as left child and/or right child.
3. The left child precedes the right child in order of children.

Binary Tree Concepts

Height and Depth in a Binary Tree: Fig. 4

Fig. 4: Height and Depth in a Binary Tree

1. Height of a node in a binary tree: is the largest no. of edges in a path from a leaf node to the target node. If the target node doesn’t have any other nodes connected to it, the height of that node would be 0.
2. Height of a binary tree: The height of a binary tree is the height of the root node in the whole binary tree. In other words, the height of a binary tree is equal to the largest number of edges from the most distant leaf node to the root (target node).
3. Depth of a node in a binary tree: The depth of a node in a binary tree is the total number of edges from the root node to the target node.
4. Depth of a binary tree: The depth of a binary tree is equal to the total number of edges from the root node to the most distant leaf node (target node).

Level in a Binary Tree: Fig. 5.

Fig. 5: Level in a Binary Tree

In a binary tree, each node has 3 elements - 1 data element and 2 children references (left and right). The topmost node of a binary tree is the root node. The level of a node is the number of edges along the unique path between the node and the root node. Therefore, the root node has a level of 0. If it has children, both of them have a level 1.

Question: Calculate a Maximum number of nodes in a binary tree at level i — mathematical formula.

Answer: The maximum number of nodes at level i is 2ˡ = n. Each node can have 2 children. If we have x nodes at a level, then each of these x nodes can have 2 children, so at the next level, we can have at most 2ˣ children.

• 0 level = 2⁰ = 1 node at this level
• 1 level = 2¹ = 2 nodes at this level
• 2 level = 2² = 4 nodes at this level
• 3 level = 2³ = 8 nodes at this level, and so on.

Note. Nodes at the same depth can be called nodes at the same level.

Question: Calculate a Minimum number of nodes in a binary tree with level i — mathematical formula.

Answer: It’s easy to see that we need at least one node for each level to construct a binary tree with level i. Therefore, the minimum number of nodes of a binary tree with level i is i+1. This binary tree is similar to a linked list, with one node connected to another. Let T be a binary tree with level n (i >= 0). Then T contains at least i+1 nodes.

Question: Calculate a Maximum number of nodes in a binary tree with level i — mathematical formula.

Answer: To construct a binary tree of level I with the maximum number of nodes, we need to make sure all internal nodes have two children. In addition, all leaf nodes must be at level i. For example, at level 0, we only have the root node. At level 1, we have 2 nodes that are the children of the root. Similarly, we have 4 nodes at level 2 who are the children of the nodes in level 1. We can see that each level doubles the number of nodes from its previous level. This is because every internal node has two children. Therefore, the maximum number of nodes of at the level i binary tree is 1+ 2 + …. 2i = 2i+1 - 1. Let T be a binary tree with level n (i >= 0). Then T contains at most 2i+1 -1 nodes.

Happy Learning

Hussain Patel