A tree is made up of nodes that are connected by either directed or undirected “edges”. The remaining nodes of the root node are known as child nodes or leaf nodes, and one of them is identified as the “Root node”. A tree is a nonlinear data structure that stores items in a hierarchy. Trees can be used to solve some of the most difficult problems in computer science. The advantage of trees is that they make efficient use of memory.
Basic Tree Terminology:
- Node: A node is an entity that contains a key or value as well as references to its child nodes.
- Root Node: The root node is the topmost node in a tree, or the node with no parent nodes.
- Parent Node: A parent node is a node that has one or more children and is the direct antecedent of that node.
- Child Node: If a node is a descendant of another node, it is referred to as a child node.
- Leaf Node: Nodes that do not have children are called leaf nodes.
- Internal Node: A node with at least one child node is called an internal node.
- Descendant: The immediate successor of the given node is called as a descendant of a node.
- Ancestor Node: Any preceding nodes on the route from the root to that node are called ancestors.
- Height of a Tree: The height of a tree is the count of edges from the root to the deepest node, or the height of the root node.
- Height of a Node: The height of a node is determined by the number of edges from the node to the deepest leaf.
- Degree of a Node: The total number of subtrees associated with this node is called the degree of the node. Degree of a leaf node must be 0.
- Level of a Node: The number of edges between the root node and that node.
- Forest: A collection of disjoint trees is called a forest.
The following section contains various C++ programs on trees, binary trees, binary search trees, expression tree, AVL tree, tree traversal, and nodes of a tree. Each sample program includes a program description, C++ code, and program output. All examples have been compiled and tested on Windows and Linux systems.
Here is the listing of C++ programming examples on Trees:
- C++ Programs on Tree
- C++ Programs on Binary Tree
- C++ Programs on Binary Search Tree
- C++ Programs on AVL Tree
- C++ Programs on Expression Tree
- C++ Programs on Nodes of a Tree
- C++ Programs on Tree Traversal
1. C++ Programs on Tree
Program | Description |
---|---|
Ternary Tree in C++ | C++ Program to Implement Ternary Tree |
Ternary Search Tree in C++ | C++ Program to Implement Ternary Search Tree |
Disjoint Set Data Structure in C++ | C++ Program to Implement Disjoint Set Data Structure |
Segment Tree in C++ | C++ Program to Implement Segment Tree |
Interval Tree in C++ | C++ Program to Implement Interval Tree |
Range Tree in C++ | C++ Program to Implement Range Tree |
Binomial Tree in C++ | C++ Program to Implement Binomial Tree |
Suffix Tree in C++ | C++ Program to Implement Suffix Tree |
B Tree in C++ | C++ Program to Implement a B Tree |
B+ Tree in C++ | C++ Program to Implement B+ Tree |
Fusion Tree in C++ | C++ Program to Implement Fusion Tree |
Prufer Code in C++ | C++ Program to Create the Prufer Code for a Tree |
2. C++ Programs on Binary Tree
Program | Description |
---|---|
AA Tree in C++ | C++ Program to Implement AA Tree |
Cartesian Tree in C++ | C++ Program to Implement Cartesian Tree |
Weight Balanced Tree in C++ | C++ Program to Implement Weight Balanced Tree |
Pagoda in C++ | C++ Program to Implement Pagoda |
Red Black Tree in C++ | C++ Program to Implement Red Black Tree |
Splay Tree in C++ | C++ Program to Implement Splay Tree |
Treap in C++ | C++ Program to Implement Treap |
Threaded Binary Tree in C++ | C++ Program to Implement Threaded Binary Tree |
ScapeGoat Tree in C++ | C++ Program to Implement ScapeGoat Tree |
Count Number of Nodes in Binary Tree in C++ | C++ Program to Count the Number of Nodes in Binary Tree |
Deepest Left Leaf Node in a Binary Tree | C++ Program to Find Deepest Left Leaf in a Binary Tree |
Mirror Image of Binary Tree in C++ | C++ Program to Create Mirror Image of a Binary Tree |
Double Order Traversal of Binary Tree in C++ | C++ Program to Implement Double Order Traversal of a Binary Tree |
Binary Tree is BST or Not in C++ | C++ Program to Check if a Binary Tree is BST or Not |
C++ Program to Check if Binary Tree is Subtree of Another Tree | C++ Program to Check if Binary Tree is Subtree of Another Tree |
Largest Independent Set in Binary Tree in C++ | C++ Program to Find the Size of Largest Independent Set (LIS) in a Binary Tree |
3. C++ Programs on Binary Search Tree
Program | Description |
---|---|
Binary Search Tree in C++ | C++ Program to Implement Binary Search Tree |
Self Balancing BST in C++ | C++ Program to Implement Self Balancing Binary Search Tree |
C++ Program to Search an Element in BST | C++ Program to Search for an Element in a Binary Search Tree |
Check if a Tree is BST in C++ | C++ Program to Check if a Tree is Binary Search Tree |
BST Min Element in C++ | C++ Program to Find the Node with Minimum Value in a Binary Search Tree |
Randomized BST in C++ | C++ Program to Implement Randomized Binary Search Tree |
AVL Tree Left and Right Rotation in C++ | C++ Program to Perform Left and Right Rotation on AVL Tree |
Lowest Common Ancestor in C++ | C++ Program to Find the Lowest Common Ancestor of a Binary Search Tree |
Balanced Binary Tree in C++ | C++ Program to Create a Balanced Binary Tree of the Incoming Data |
BST Dictionary Operations in C++ | C++ Program to Perform Dictionary Operations in a Binary Search Tree |
4. C++ Programs on AVL Tree
Program | Description |
---|---|
AVL Tree in C++ | C++ Program to Implement AVL Tree |
BST is AVL Tree or Not in C++ | C++ Program to Check if a Binary Tree is an AVL Tree or Not |
AVL Tree Operations in C++ | C++ Program to Perform AVL Tree Operations |
5. C++ Programs on Expression Tree
Program | Description |
---|---|
Expression Tree in C++ | C++ Program to Implement Expression Tree |
Create Expression Tree from Prefix Expression in C++ | C++ Program to Create Expression Tree from Prefix Expression |
Create Expression Tree from Postfix Expression in C++ | C++ Program to Create Expression Tree from Postfix Expression |
Create Expression Tree from Infix Expression in C++ | C++ Program to Create Expression Tree from Infix Expression |
6. C++ Programs on Nodes of a Tree
Program | Description |
---|---|
C++ Program to Count Leaf Nodes in a Tree | C++ Program to Count Leaf Nodes in a Binary Search Tree |
C++ Program to Count Internal Nodes in a Tree | C++ Program to Count All Internal Nodes in a Binary Search Tree |
Print the Nodes at Odd Levels of a Tree in C++ | C++ Program to Print the Nodes at Odd Levels of a Tree |
K-sum Paths in a Binary Tree in C++ | C++ Program to Remove All nodes which don’t lie in Any Path with Sum >= K |
7. C++ Programs on Tree Traversal
Program | Description |
---|---|
Inorder Tree Traversal without Recursion in C++ | C++ Program for Inorder Tree Traversal without Recursion |
Level Order Traversal using Recursion in C++ | C++ Program for Level Order Traversal of a Tree using Recursion |
Spiral Order Traversal using Recursion in C++ | C++ Program for Spiral Order Traversal of a Tree using Recursion |
Inorder Traversal using Recursion in C++ | C++ Program to Perform Inorder Traversal of a Binary Tree using Recursion |
Preorder Traversal using Recursion in C++ | C++ Program to Perform Preorder Traversal of a Binary Tree using Recursion |
Preorder Traversal without Recursion in C++ | C++ Program to Perform Preorder Traversal of a Binary Tree without using Recursion |
Postorder Traversal using Recursion in C++ | C++ Program to Perform Postorder Traversal of a Binary Tree using Recursion |
Postorder Traversal without Recursion in C++ | C++ Program to Perform Postorder Traversal of a Binary Tree without using Recursion |