Binary Trees | Data Structures & Algorithms
Binary Trees
Data Structures & Algorithms — Complete Study Notes
1. Introduction to Binary Trees
A Binary Tree is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child. It is one of the most fundamental structures in
Data Structures and is widely used in searching, sorting, expression parsing, and hierarchical
data representation.
Each node in a binary tree contains:
• Data (value)
• Pointer to left child
• Pointer to right child
1.1 Basic Terminologies
• Root: The top-most node of the tree
• Leaf Node: Node with no children
• Internal Node: Node with at least one child
• Height of Tree: Longest path from root to a leaf
• Depth of Node: Distance from root to that node
2. Logical Construction of Binary Trees
Logical construction means how we represent and build a binary tree in memory using
programming concepts.
2.1 Node Structure in C++
To construct a binary tree, we first define a node:
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
// Constructor
Node(int val) {
Page 1 of 7
, Binary Trees | Data Structures & Algorithms
data = val;
left = NULL;
right = NULL;
}
};
Explanation:
• data stores the value
• left and right are pointers to child nodes
• Constructor initializes node values
2.2 Manual Construction of Binary Tree
Question Statement
Create a binary tree manually with values:
10
/ \
5 20
/ \ \
3 7 25
Program Example
int main() {
// Creating nodes
Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(20);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->right->right = new Node(25);
cout << "Binary Tree Created Successfully!";
return 0;
}
Explanation:
• We manually connect nodes using pointers
• This is called linked representation
• Tree structure is explicitly defined
2.3 Dynamic Construction (User Input Based)
Tree can also be built dynamically using recursion.
Node* createTree() {
Page 2 of 7
Binary Trees
Data Structures & Algorithms — Complete Study Notes
1. Introduction to Binary Trees
A Binary Tree is a hierarchical data structure in which each node has at most two children,
referred to as the left child and the right child. It is one of the most fundamental structures in
Data Structures and is widely used in searching, sorting, expression parsing, and hierarchical
data representation.
Each node in a binary tree contains:
• Data (value)
• Pointer to left child
• Pointer to right child
1.1 Basic Terminologies
• Root: The top-most node of the tree
• Leaf Node: Node with no children
• Internal Node: Node with at least one child
• Height of Tree: Longest path from root to a leaf
• Depth of Node: Distance from root to that node
2. Logical Construction of Binary Trees
Logical construction means how we represent and build a binary tree in memory using
programming concepts.
2.1 Node Structure in C++
To construct a binary tree, we first define a node:
#include <iostream>
using namespace std;
// Node structure
struct Node {
int data;
Node* left;
Node* right;
// Constructor
Node(int val) {
Page 1 of 7
, Binary Trees | Data Structures & Algorithms
data = val;
left = NULL;
right = NULL;
}
};
Explanation:
• data stores the value
• left and right are pointers to child nodes
• Constructor initializes node values
2.2 Manual Construction of Binary Tree
Question Statement
Create a binary tree manually with values:
10
/ \
5 20
/ \ \
3 7 25
Program Example
int main() {
// Creating nodes
Node* root = new Node(10);
root->left = new Node(5);
root->right = new Node(20);
root->left->left = new Node(3);
root->left->right = new Node(7);
root->right->right = new Node(25);
cout << "Binary Tree Created Successfully!";
return 0;
}
Explanation:
• We manually connect nodes using pointers
• This is called linked representation
• Tree structure is explicitly defined
2.3 Dynamic Construction (User Input Based)
Tree can also be built dynamically using recursion.
Node* createTree() {
Page 2 of 7
