W Code - Pattern-Based DSA Learning Platform

Bhanu Bisht

Back to DSA Theory

Trees

Hierarchical data structure - Binary Trees, BST, Traversals and more.

What is a Tree?

Depends on tree type and operation

Hierarchical Data Modeling

Unlike linear data structures (arrays, linked lists, stacks, queues) that organize values sequentially, a Tree is a non-linear hierarchical data structure. Think of a corporate organization chart: the CEO (root) sits at the top, branching down to Vice Presidents (parents), who supervise managers, down to individual contributors (leaves).

Key Terminology:

Root: The single topmost node in the tree (has no parent).
Parent: A node that has links pointing to nodes below it.
Child: A node connected to a predecessor node above it.
Leaf Node: A node situated at the bottom margins that has zero children.
Height: The number of edges along the longest path from a given node down to a leaf. (Height of root = height of tree).
Depth: The number of edges from the root node to a target node.

Real-world Systems:

File Systems: Folders nesting sub-folders down to files.
DOM Structure: HTML parent tags wrapping nested child tags.
Decision Systems: Classification trees dividing datasets based on conditions.

C++ Code — What is a Tree?

#include <iostream>
using namespace std;

// Basic Tree Node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

int main() {
    // Create a simple binary tree
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    cout << "Root: " << root->data << endl;
    cout << "Left child: " << root->left->data << endl;
    cout << "Right child: " << root->right->data << endl;
    
    return 0;
}

Binary Tree & Binary Search Tree

BST - Search/Insert/Delete: O(log n) average, O(n) worst

Structures & Constraints

Trees are customized by placing rules on branching boundaries:

1. Binary Tree (BT)

A tree where each node is restricted to a maximum of two children, called left and right child.

Full Binary Tree: Every node has either exactly 0 or 2 children.
Complete Binary Tree: All levels are completely filled, except possibly the last, which is filled from left to right.
Perfect Binary Tree: All leaves sit on the exact same depth, and all internal nodes have exactly two children.
Balanced Binary Tree: The height of the left and right subtrees of any node differs by at most 1.

2. Binary Search Tree (BST)

A binary tree configured with an ordering sorting property:

The left subtree of a node contains values strictly less than that node's value.
The right subtree of a node contains values strictly greater than that node's value.
This rule applies recursively to all subtrees.
Time Complexity: Search, Insertion, and Deletion run in O(log n) on average. However, if the tree becomes skewed (like a linked list), complexity degrades to O(n).

C++ Code — Binary Tree & Binary Search Tree

#include <iostream>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

class BST {
public:
    TreeNode* root;
    
    BST() : root(nullptr) {}
    
    // Insert into BST
    TreeNode* insert(TreeNode* node, int val) {
        if (node == nullptr) {
            return new TreeNode(val);
        }
        
        if (val < node->data) {
            node->left = insert(node->left, val);
        } else {
            node->right = insert(node->right, val);
        }
        return node;
    }
    
    void insert(int val) {
        root = insert(root, val);
    }
    
    // Search in BST
    bool search(TreeNode* node, int val) {
        if (node == nullptr) return false;
        if (node->data == val) return true;
        
        if (val < node->data) {
            return search(node->left, val);
        } else {
            return search(node->right, val);
        }
    }
    
    bool search(int val) {
        return search(root, val);
    }
    
    // Inorder traversal (gives sorted order for BST)
    void inorder(TreeNode* node) {
        if (node == nullptr) return;
        inorder(node->left);
        cout << node->data << " ";
        inorder(node->right);
    }
};

int main() {
    BST tree;
    tree.insert(50);
    tree.insert(30);
    tree.insert(70);
    tree.insert(20);
    tree.insert(40);
    
    cout << "Inorder (sorted): ";
    tree.inorder(tree.root);
    cout << endl;  // 20 30 40 50 70
    
    cout << "Search 40: " << (tree.search(40) ? "Found" : "Not Found") << endl;
    cout << "Search 100: " << (tree.search(100) ? "Found" : "Not Found") << endl;
    
    return 0;
}

Tree Traversals

All traversals: O(n) time, O(h) space for recursive (h = height)

Traversal Algorithms

Traversal is the process of visiting all nodes in a tree exactly once. Unlike linear data structures, trees can be traversed in multiple ways:

1. Depth-First Search (DFS)

Inorder (Left → Root → Right):
- BST Benefit: Yields elements in ascending sorted order.
Preorder (Root → Left → Right):
- Usage: Creating copies of trees, generating prefix notation.
Postorder (Left → Right → Root):
- Usage: Bottom-up deletion of tree nodes, evaluating postfix notations.

2. Breadth-First Search (BFS)

Level Order Traversal:
- Visits nodes level-by-level starting from root, traversing left-to-right.
- Implementation: Uses a Queue container to track visited parent nodes.

C++ Code — Tree Traversals

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Inorder: Left -> Root -> Right
void inorder(TreeNode* node) {
    if (node == nullptr) return;
    inorder(node->left);
    cout << node->data << " ";
    inorder(node->right);
}

// Preorder: Root -> Left -> Right
void preorder(TreeNode* node) {
    if (node == nullptr) return;
    cout << node->data << " ";
    preorder(node->left);
    preorder(node->right);
}

// Postorder: Left -> Right -> Root
void postorder(TreeNode* node) {
    if (node == nullptr) return;
    postorder(node->left);
    postorder(node->right);
    cout << node->data << " ";
}

// Level Order (BFS)
void levelOrder(TreeNode* root) {
    if (root == nullptr) return;
    
    queue<TreeNode*> q;
    q.push(root);
    
    while (!q.empty()) {
        TreeNode* node = q.front();
        q.pop();
        cout << node->data << " ";
        
        if (node->left) q.push(node->left);
        if (node->right) q.push(node->right);
    }
}

int main() {
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    
    cout << "Inorder:    "; inorder(root);    cout << endl;  // 4 2 5 1 3
    cout << "Preorder:   "; preorder(root);   cout << endl;  // 1 2 4 5 3
    cout << "Postorder:  "; postorder(root);  cout << endl;  // 4 5 2 3 1
    cout << "Level Order: "; levelOrder(root); cout << endl; // 1 2 3 4 5
    
    return 0;
}

Height, Depth & Diameter

Height: O(n) | Balanced: O(n) | Diameter: O(n)

Distance Metrics

Evaluating properties of tree structures is a common focal point in interviews:

1. Tree Height Calculation (`O(n)` Time)

The height of a node is calculated recursively: height = 1 + max(height(left), height(right))

Base Case: A null node returns -1 (or 0 depending on edge-count definition).

2. Balanced Validation (`O(n)` Time)

A tree is height-balanced if the left and right subtrees are balanced, and the height difference at the current node is at most 1. We can optimize this check by calculating height and balance status in a single recursive pass.

3. Tree Diameter (`O(n)` Time)

The Diameter (or width) of a tree is the length of the longest path between any two nodes. The path may or may not pass through the root.

Optimized Check: At each node, compute the sum of left and right heights. The maximum sum found across all nodes represents the diameter.

C++ Code — Height, Depth & Diameter

#include <iostream>
#include <algorithm>
using namespace std;

struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};

// Height of tree
int height(TreeNode* node) {
    if (node == nullptr) return -1;  // or 0 depending on definition
    
    int leftHeight = height(node->left);
    int rightHeight = height(node->right);
    
    return 1 + max(leftHeight, rightHeight);
}

// Check if balanced (height diff <= 1 for all nodes)
int checkBalance(TreeNode* node, bool& balanced) {
    if (node == nullptr) return -1;
    
    int leftH = checkBalance(node->left, balanced);
    int rightH = checkBalance(node->right, balanced);
    
    if (abs(leftH - rightH) > 1) {
        balanced = false;
    }
    
    return 1 + max(leftH, rightH);
}

bool isBalanced(TreeNode* root) {
    bool balanced = true;
    checkBalance(root, balanced);
    return balanced;
}

// Diameter of tree (optimized - O(n))
int diameterHelper(TreeNode* node, int& diameter) {
    if (node == nullptr) return 0;
    
    int leftH = diameterHelper(node->left, diameter);
    int rightH = diameterHelper(node->right, diameter);
    
    // Update diameter if path through this node is longer
    diameter = max(diameter, leftH + rightH);
    
    return 1 + max(leftH, rightH);
}

int diameter(TreeNode* root) {
    int dia = 0;
    diameterHelper(root, dia);
    return dia;
}

int main() {
    //       1
    //      / \
    //     2   3
    //    / \
    //   4   5
    //  /
    // 6
    
    TreeNode* root = new TreeNode(1);
    root->left = new TreeNode(2);
    root->right = new TreeNode(3);
    root->left->left = new TreeNode(4);
    root->left->right = new TreeNode(5);
    root->left->left->left = new TreeNode(6);
    
    cout << "Height: " << height(root) << endl;      // 3
    cout << "Balanced: " << (isBalanced(root) ? "Yes" : "No") << endl;  // No
    cout << "Diameter: " << diameter(root) << endl;  // 4 (path: 6-4-2-5 or 6-4-2-1-3)
    
    return 0;
}

#include <iostream> using namespace std; // Basic Tree Node struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; int main() { // Create a simple binary tree // 1 // / \ // 2 3 // / \ // 4 5 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "Root: " << root->data << endl; cout << "Left child: " << root->left->data << endl; cout << "Right child: " << root->right->data << endl; return 0; }

#include <iostream> using namespace std; struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; class BST { public: TreeNode* root; BST() : root(nullptr) {} // Insert into BST TreeNode* insert(TreeNode* node, int val) { if (node == nullptr) { return new TreeNode(val); } if (val < node->data) { node->left = insert(node->left, val); } else { node->right = insert(node->right, val); } return node; } void insert(int val) { root = insert(root, val); } // Search in BST bool search(TreeNode* node, int val) { if (node == nullptr) return false; if (node->data == val) return true; if (val < node->data) { return search(node->left, val); } else { return search(node->right, val); } } bool search(int val) { return search(root, val); } // Inorder traversal (gives sorted order for BST) void inorder(TreeNode* node) { if (node == nullptr) return; inorder(node->left); cout << node->data << " "; inorder(node->right); } }; int main() { BST tree; tree.insert(50); tree.insert(30); tree.insert(70); tree.insert(20); tree.insert(40); cout << "Inorder (sorted): "; tree.inorder(tree.root); cout << endl; // 20 30 40 50 70 cout << "Search 40: " << (tree.search(40) ? "Found" : "Not Found") << endl; cout << "Search 100: " << (tree.search(100) ? "Found" : "Not Found") << endl; return 0; }

#include <iostream> #include <queue> using namespace std; struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; // Inorder: Left -> Root -> Right void inorder(TreeNode* node) { if (node == nullptr) return; inorder(node->left); cout << node->data << " "; inorder(node->right); } // Preorder: Root -> Left -> Right void preorder(TreeNode* node) { if (node == nullptr) return; cout << node->data << " "; preorder(node->left); preorder(node->right); } // Postorder: Left -> Right -> Root void postorder(TreeNode* node) { if (node == nullptr) return; postorder(node->left); postorder(node->right); cout << node->data << " "; } // Level Order (BFS) void levelOrder(TreeNode* root) { if (root == nullptr) return; queue<TreeNode*> q; q.push(root); while (!q.empty()) { TreeNode* node = q.front(); q.pop(); cout << node->data << " "; if (node->left) q.push(node->left); if (node->right) q.push(node->right); } } int main() { // 1 // / \ // 2 3 // / \ // 4 5 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); cout << "Inorder: "; inorder(root); cout << endl; // 4 2 5 1 3 cout << "Preorder: "; preorder(root); cout << endl; // 1 2 4 5 3 cout << "Postorder: "; postorder(root); cout << endl; // 4 5 2 3 1 cout << "Level Order: "; levelOrder(root); cout << endl; // 1 2 3 4 5 return 0; }

#include <iostream> #include <algorithm> using namespace std; struct TreeNode { int data; TreeNode* left; TreeNode* right; TreeNode(int val) : data(val), left(nullptr), right(nullptr) {} }; // Height of tree int height(TreeNode* node) { if (node == nullptr) return -1; // or 0 depending on definition int leftHeight = height(node->left); int rightHeight = height(node->right); return 1 + max(leftHeight, rightHeight); } // Check if balanced (height diff <= 1 for all nodes) int checkBalance(TreeNode* node, bool& balanced) { if (node == nullptr) return -1; int leftH = checkBalance(node->left, balanced); int rightH = checkBalance(node->right, balanced); if (abs(leftH - rightH) > 1) { balanced = false; } return 1 + max(leftH, rightH); } bool isBalanced(TreeNode* root) { bool balanced = true; checkBalance(root, balanced); return balanced; } // Diameter of tree (optimized - O(n)) int diameterHelper(TreeNode* node, int& diameter) { if (node == nullptr) return 0; int leftH = diameterHelper(node->left, diameter); int rightH = diameterHelper(node->right, diameter); // Update diameter if path through this node is longer diameter = max(diameter, leftH + rightH); return 1 + max(leftH, rightH); } int diameter(TreeNode* root) { int dia = 0; diameterHelper(root, dia); return dia; } int main() { // 1 // / \ // 2 3 // / \ // 4 5 // / // 6 TreeNode* root = new TreeNode(1); root->left = new TreeNode(2); root->right = new TreeNode(3); root->left->left = new TreeNode(4); root->left->right = new TreeNode(5); root->left->left->left = new TreeNode(6); cout << "Height: " << height(root) << endl; // 3 cout << "Balanced: " << (isBalanced(root) ? "Yes" : "No") << endl; // No cout << "Diameter: " << diameter(root) << endl; // 4 (path: 6-4-2-5 or 6-4-2-1-3) return 0; }

Trees

What is a Tree?

Hierarchical Data Modeling

Key Terminology:

Real-world Systems:

Binary Tree & Binary Search Tree

Structures & Constraints

1. Binary Tree (BT)

2. Binary Search Tree (BST)

Tree Traversals

Traversal Algorithms

1. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

Height, Depth & Diameter

Distance Metrics

1. Tree Height Calculation (O(n) Time)

2. Balanced Validation (O(n) Time)

3. Tree Diameter (O(n) Time)

Trees

What is a Tree?

Hierarchical Data Modeling

Key Terminology:

Real-world Systems:

Binary Tree & Binary Search Tree

Structures & Constraints

1. Binary Tree (BT)

2. Binary Search Tree (BST)

Tree Traversals

Traversal Algorithms

1. Depth-First Search (DFS)

2. Breadth-First Search (BFS)

Height, Depth & Diameter

Distance Metrics

1. Tree Height Calculation (O(n) Time)

2. Balanced Validation (O(n) Time)

3. Tree Diameter (O(n) Time)

1. Tree Height Calculation (`O(n)` Time)

2. Balanced Validation (`O(n)` Time)

3. Tree Diameter (`O(n)` Time)

1. Tree Height Calculation (`O(n)` Time)

2. Balanced Validation (`O(n)` Time)

3. Tree Diameter (`O(n)` Time)