Trees

16 Jul, 2025

What are Trees ?

Trees are just singly linked lists with extra pointers ! Ok jokes aside Trees are non-linear data structure used to represent and store data in a hierarchical order.

So this is a tree :

			     10  <- This is root node
			   /   \
			 5      12  <-This is a Node
			/ \    /  \
		       2   4  11   17

Similarly like Linked Lists tree nodes can be anywhere in the memory and are connected using node pointers. Its a chaos in memory but structure in code.

Building a Tree Node Structure

The basic structure of a node of a tree can be made using structs like this:

typedef struct node{
    int data; //data
    struct node* left; //left child
    struct node* right; //right child

    node(){} //default constructor
    node(int val) : data(val), left(nullptr), right(nullptr) {} //parameterized constructor

}node;

This can be stack allocated and heap allocated. Mainly trees are heap allocated as they don't have fixed sizes like arrays and are used for hierarchical and growing data. Meanwhile allocating on the stack is okay for smaller fixed sized trees but we will be allocating them on the heap because then we wont have the memory constraint big of an issue.

Lets allocate on Stack and Heap

Stack allocation:

int main(){

    node root(7);
    node leftChild(3);
    node rightChild(8);

    root.left = &leftChild;
    root.right = &rightChild;
  
    std::cout << root.data << std::endl; //7
    std::cout << root.left->data << std::endl; //3
    std::cout << root.right->data << std::endl; //8

    return 0;
}

Heap allocation:

int main(){

    node* root = new node(6);
    root->left = new node(13);
    root->right = new node(17);

    std::cout << root->data << std::endl; //6
    std::cout << root->left->data << std::endl; //13
    std::cout << root->right->data << std::endl; //17
  
    delete root->left;
    delete root->right;
    delete root;

    return 0;
}

Tree Terminologies

🧷 Some key points

By definitions, A tree is a collection of nodes with one root and zero or more children . Hence,

• Every Valid Tree is a sub-tree.
• Every sub-tree is a Valid tree.
• A single node is also a Valid tree and a sub-tree.

🔹 Traversing a Tree

Traversing = Visiting each Node or element (in arrays).

Trees are said to be recursive in nature, means we can actively use recursion to build or traverse them.

We can traverse or search using 2 main techniques:

1. Depth First Search (DFS) : We start from root and pick an edge trail i.e. either left or right then we continue to traverse down that edge, we don't visit any sibling nodes. We continue to go left or right until we hit a leaf node. Then from root we pick another edge trail and follow. We first go full depth than breadth.

2. Breadth First Search (BFS) : We start from root and unlike DFS we visit each child node of the root node, i.e. we complete one full sub tree before moving down and follow the same method throughout the process. We got breadth first than depth.

👀 Now I did try to traverse a tree without recursion, see here 👉🏼 My attempt to traverse a tree without recursion.

In the case of Trees. We got the Big 3 Traversals:

1. InOrder (L -> Root -> R) : First Left Node then Root Node then Right Node.
2. PreOrder (Root -> L -> R) : First Root Node then Left Node then Right Node.
3. PostOrder (L -> R -> Root) : First Left Node then Right Node then Root Node.

KEY OBSERVATION: All the traversal change how we visit root node. We always visit the left node before the right one ! We are shifting Root !

Lets see each traversal technique.

🔸 DFS

1. PreOrder (Root -> L -> R) :

//PreOrder (Root -> Left -> Right)
void DFS_PreOrder(node* root){
    if(root == nullptr) return; //base case

    std::cout << root->data << std::endl;

    //call DFS_PreOrder() passing both left and right children as root of sub trees
    DFS_PreOrder(root->left);
    DFS_PreOrder(root->right);
}

2. InOrder (L -> Root -> R) :

//InOrder (Left -> Root -> Right)
void DFS_InOrder(node* root){
    if(root == nullptr) return; //base case

    //calling DFS_InOrder() passing left child as root of left sub tree
    DFS_InOrder(root->left);
  
    std::cout << root->data << std::endl;
    
    //calling DFS_InOrder() passing right child as root of right sub tree
    DFS_InOrder(root->right);
}

3. PostOrder (L -> R -> Root) :

//PostOrder (Left -> Right -> Root)
void DFS_PostOrder(node* root){
    if(root == nullptr) return; //base case

    //calling DFS_InOrder() passing left child as root of left sub tree
    DFS_PostOrder(root->left);

    //calling DFS_InOrder() passing right child as root of right sub tree
    DFS_PostOrder(root->right);

    std::cout << root->data << std::endl;
}

🔸 BFS

Now BFS does not vibe naturally with recursion like DFS does. We can still use recursion but for this one I did the conventional non-recursive approach. This is my version of the code.

void BFS(node* root){

    //store the root
    std::vector<node*> nodeList_queue = { root };

    node* pointer = nodeList_queue[0]; //point to the first element of the vector queue.
    int index = 1;

    while(true){
        //if there is no more children left to traverse
        if(!pointer->left || !pointer->right) break;

        //push the children in the vector queue
        nodeList_queue.push_back(pointer->left);
        nodeList_queue.push_back(pointer->right);

        pointer = nodeList_queue[index++];
    }

    for(int x = 0; x < nodeList_queue.size(); x++){
        std::cout << nodeList_queue[x]->data << std::endl;
    }
}

Although this only works for trees with exactly 2 or 0 children. WILL TWEAK LATER.

#CPP #Data Structures And Algorithms