Binary Tree Data Structure in C++

A Binary Tree is a hierarchical data structure in which each node has at most two children, referred to as left child and right child. A binary tree can represent various problems, including hierarchical data, searching, and sorting.

Representation of Binary Tree.

In a binary tree, each node contains a value, and it has two pointers to the left and right child nodes. If a child node does not exist, the pointer is null. The root node is the topmost node of the tree, and it has no parent. The leaf nodes are nodes that have no children, and they are at the bottom of the tree.

A binary tree can be represented in two ways: 

• Array-based: In the array-based representation, the tree is stored in an array, and the position of each node is determined based on its index.

• Node-based: In the node-based representation, each node is stored in a separate object, and it contains pointers to its children.

In C++ we represent a tree node of a tree we use structure or class.  

// Method 1: Using "struct" to make
struct Node {
	int data;
	struct Node* left;
	struct Node* right;
};

// Method 2: Using "class" to make
class Node {
public:
	int data;
	Node* left;
	Node* right;
};

Usage of Binary Tree.

• Hierarchical Data: Binary Trees are used to represent hierarchical data such as family trees, organization charts, file systems, and more.

• Searching: Binary Trees can be used to perform efficient searching of data. Binary search trees, a type of binary tree, provide fast searching and insertion operations.

• Sorting: Binary Trees can be used for sorting data efficiently. Heaps, a type of binary tree, are used for heap sort and priority queues.

• Compression: Binary Trees are used in data compression algorithms such as Huffman coding.

Some Important Terms Used in Tree Data Structure.

• Node: A node is a basic unit of a tree that contains data and pointers to its child nodes.

• Root: The root is the topmost node of a tree, from which all other nodes are descendants.

• Parent: A parent is a node that has one or more child nodes.

• Child: A child is a node that has a parent node.

• Sibling: Siblings are nodes that have the same parent node.

• Leaf: A leaf is a node that has no children.

• Height: The height of a tree is the length of the longest path from the root node to the leaf node.

• Depth: The depth of a node is the length of the path from the root node to that node.

• Degree: The degree of a node is the number of children it has.

• Subtree: A subtree is a tree that is formed by a node and all its descendants.

• Binary Tree: A binary tree is a tree data structure in which each node has at most two children.

• Balanced Tree: A balanced tree is a tree data structure in which the height of the left and right subtrees of any node differ by at most one.

• Traversal: Traversal refers to the process of visiting every node in a tree data structure exactly once.

• Search: Search refers to the process of finding a specific node in a tree data structure.

• Insertion: Insertion refers to the process of adding a new node to a tree data structure.

Advantage of Binary Tree.

• Fast Search: Binary Trees provide fast searching of data as they have a logarithmic time complexity of O(log n).

• Efficient Storage: Binary Trees use memory efficiently as they only store the data and the pointers to their children.

• Easy Traversal: Binary Trees can be easily traversed in different ways such as Inorder, Preorder, and Postorder.

• Flexible: Binary Trees can be easily modified by adding, deleting, or updating nodes.

• Balanced Trees: Balanced Binary Trees such as AVL Trees and Red-Black Trees provide efficient searching, insertion, and deletion operations.

Binary Tree Important Definition and Properties.

 

Tree: Non-Linear Data Structure in which data is organized in a hierarchical manner.  It is very fast for information retrieval and searching operations. 

Important Terminology of a Binary Tree.

Node: Each element in a tree is called a node.

Edges: Lines connecting two nodes, it is also known as branches. 

Parent Node: The immediate predecessor of a node (node that comes just before a node).

Child Node: The immediate successors of a node (node that comes just next in line).

Root Node: The node that doesn't have any parent node.

Leaf Node: The node that doesn't have any child node. The node other than the leaf node is known as a non-leaf or terminal node. 

Level: Distance of that node from the root.

Height: Total number of level, depth of the tree, Level+1=Height

Siblings: All nodes having the same parent. All siblings are at the same level but it is not necessary that nodes at the same level are siblings.

Path: It is a way to reach a node from any other node. In a tree, there is only one path possible between any two nodes. Path length = Number of Edges on the path.

Degree: The number of children or subtrees connected to a node.

Forest: The subtrees we get after removing the root of the main tree is collectively called as Forest (also known as a set of disjoint trees).  

Strictly Binary Tree: Each node in the tree is either a leaf node or has exactly two children. There is no node with one child. 

Extended Binary tree: Each Empty subtree is replaced by a special node then the resulting tree is extended binary tree or 2-tree.

Full Binary tree: All the levels have the maximum number of nodes.

**If the number of any node is k, then the number of the left child is 2k, the number of right children is 2k+1, and the number of its parent is k/2.

Complete Binary Tree: All the levels have the maximum number of nodes except possibly the last node.

Important Properties of a Binary Tree.

P1. The maximum number of nodes possible on any level i is 2^i where i>=0.

P2. The maximum number of nodes possible in a binary tree of height h is 2^h-1.

P3. The minimum number of nodes possible in a binary tree of height h is equal to h. A tree with a minimum number of nodes is called skew trees.

P4. If a binary tree contains n nodes, then its maximum height possible is n and the minimum height possible is log2(n+1).

P5. In a non-empty binary tree, if n is the total number of nodes and e is the total number of edges, then e = n-1.

P6. In a non-empty binary tree, if n is the number of nodes with no child and m is the number of nodes with 2 children, then n = m+1.

Traversal in Binary Tree

1. Breadth-First Traversal (Level Order Traversal)

2. Depth First Traversal

A. Preorder Traversal (Root, Left, Right)

B. Inorder Traversal (Left, Root, Right)

C. Postorder Traversal (Left, Right, Root)