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

Trees are one of the most common data structure 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 about tree, then learn about binary tree along with an implementation of binary tree — the Binary Search Tree also knows as BST.

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

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

Some of the terminologies used in a Tree structure are:

1. Each node has a value, also referred to as key value.

2. The top node of a tree is call Root node. If node is connected by edge to other node, the top node is called the parent and the node below is called its children.

3. A pair of node (p,c) is connected by an edge, edge always has 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 is at Level 1, those nodes children are at Level 2 and so on. We can define depth of a tree as 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 root node will have exactly 1 incoming edge.

Question: Can a tree be empty?

Answer: Yes — a tree which 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’s (i.e. 0, 1 or at max 2 children’s). Fig. 3

Binary tree has 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. Left child precedes right child in order of children.

Binary Tree Concepts:

Height and Depth in a Binary Tree: Fig. 4

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

In a binary tree each node has 3 element — 1 data element and 2 children references (left and right). The top most 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’s, both of them have a level 1.

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

Answer: Maximum number of nodes at level i is 2ˡ = n. Each node can have 2 children’s, if we have x nodes at a level, then each of these x nodes can have 2 children’s, so at next level we can have at most 2ˣ children’s

0 level = 2⁰ = 1 nodes 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 same depth can be called as nodes at same level.

Question: Calculate Minimum number of nodes in 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, 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 Maximum number of nodes in 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 the 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 level i binary tree is 1+ 2 + …. 2ˡ = 2ˡ+1 -1. Let T be a binary tree with level n (i >= 0). Then T contains at most 2ˡ+1 -1 nodes.