Mastering Binary Trees for Competitive Programming and Online Assessments

Welcome to a comprehensive six-part series dedicated to mastering binary trees. In this carefully crafted journey, we will cover the basics of binary trees step by step and deep dive into interview questions that will sharpen your problem-solving skills. Whether you're preparing for technical interviews or looking to solidify your understanding of this fundamental data structure, this series is your roadmap to success. Let's start on this educational adventure together!

Fundamental concept of Binary tree

At its core, a binary tree is a hierarchical data structure composed of nodes. Each node can have at most two children, aptly named the left child and the right child. These children, in turn, can have their own children, forming a tree-like structure.

Basic terminologies related to Binary tree:
Root Node: The topmost node in a binary tree is called the root. It serves as the starting point for traversing the tree.

Node: Every element in a binary tree is a node. A node can hold data, often referred to as the "value" or "key," and it can have references to its left and right children.
Parent and Child Nodes: A node can be a parent to its immediate children. Conversely, those children are referred to as the parent's left and right children.
Leaf Node: A leaf node is one that doesn't have any children. It's essentially a node at the fringe of the tree.
Depth and Height: The depth of a node is the length of the path from the root to that node. The height of the tree is the maximum depth among all nodes.
Subtree: A subtree is a smaller binary tree formed by a node and all its descendants.

        10 <-- Root Node
       /  \
      5    15 
     / \  / \
    3   7 12 18<--Leaf Nodes

Let's visualize these concepts with a few simple examples:

Single Node: The smallest binary tree consists of just one node, which is both the root and the leaf.
```
    5
```
Balanced Binary Tree: In a balanced binary tree, each node has either zero or two children, and the heights of the subtrees differ by at most one.
```
      10
     /  \
    5    15
   / \  / \
  3   7 12 18
```
Unbalanced Binary Tree: An unbalanced binary tree can have varying heights for its left and right subtrees.
```
      10
     /  
    5    
   /   
  3
```

Essential basic question

1. In-Order Traversal:

Question: Implement an in-order traversal of a binary tree.
Explanation: In an in-order traversal, you visit the left subtree, then the current node, and finally the right subtree.

void Inoder(node* root){
//base case when root is null , you have to just return
if(root==NULL){
return;
}
//recurively calling for the traversal of the left part
Inorder(root->left);
//print the data of the root
cout<<root->data;
//recursive calling for the right part
Inorder(root->right);
}

2. Pre-Order Traversal:

Question: Implement a pre-order traversal of a binary tree.

Explanation: In a pre-order traversal, you visit the current node and print it , then the left subtree, and finally the right subtree.

  void Preoder(node* root){
  //base case 
  if(root==NULL){
  rerurn 
  }
  //print the cuurent data of node
  cout<<node->data;
  //recursivlly call the left subtree
  Preorder(root->left);
  //recursive calling of the right subtree
  Preorder(root->right);
  }

3. Post-Order Traversal:

Question: Implement a post-order traversal of a binary tree.
Explanation: In a post-order traversal, you visit the left subtree, then the right subtree, and finally the current node.

    void Postorder(node* root){
    //base case
    if(root==NULL){
    return 
    }
    //recursvive calling of left subtree
    Postorder(root->left);
    //recursive calling of the right subtree
    Postorder(root->right);
    cout<<root->data;
    }

4. Level-Order Traversal:

Question: Implement a level-order (breadth-first) traversal of a binary tree.
Explanation: In a level-order traversal, you visit nodes level by level, from left to right, starting from the root.

    void levelorder(node* root){
    //base case for empty tree  
    if(root==NULL){
    return;
    }
    //create a queue 
    queue<node*> q;
    q.push(root);
    while(1q.empty()){
    node* current=q.front();
    q.pop();
    cout<<current->data;
    //now time to put the data of left subtree of current
    //into queue if it exists.
    if(cuurent->left!=NULL){
    q.push(current->left);}
    //after this if right subtree exits for current node
    if(cuurent->right!=NULL){
    q.push(current->right)}
    }

5. Find the Height of a Binary Tree:

Question: Write a function to find the height (or depth) of a binary tree.
Explanation: The height of a binary tree is the length of the longest path from the root to a leaf node.

    int height(node* root){
    //base case return 0 and store it so that later we can add 
    if(root==NULL){
    return 0;
    }
    //go recursively left and store it into some variable
    int left=height(root->left);
    //similarly, go recursively right and store into variable
    int right=height(root->right);
    //while returning the node 
    return max(left+right)+1;

6. Validate a Binary Search Tree (BST):

Question: Given a binary tree, determine whether it's a valid Binary Search Tree (BST).
Explanation: In a valid BST, for every node, values in its left subtree are less than its value, and values in its right subtree are greater.

    bool isValidate(TreeNode* root, long long minValue, long long maxValue) {
        // Base case: If the tree is empty, it's a valid BST.
        if (root == nullptr) {
            return true;
        }

        // Check if the current node's value is within the valid range.
        if (root->value <= minValue || root->value >= maxValue) {
            return false;
        }

        // Recursively check the left and right subtrees.
        // Update the valid range for each subtree.
        return isValidate(root->left, minValue, root->value) &&
               isValidate(root->right, root->value, maxValue);
    }

    bool isValidBST(TreeNode* root) {
        return isValidate(root, LLONG_MIN, LLONG_MAX);
    }

7. Find the Lowest Common Ancestor (LCA):

Question: Given two nodes in a binary tree, find their lowest common ancestor.
Explanation: The lowest common ancestor of two nodes is the shared ancestor farthest from the root.

    TreeNode* findLCA(TreeNode* root, TreeNode* p, TreeNode* q) {
        // Base case: If the tree is empty or one of the nodes is found, return the current node.
        if (root == nullptr || root == p || root == q) {
            return root;
        }

        // Recursively search for the LCA in the left and right subtrees.
        TreeNode* leftLCA = findLCA(root->left, p, q);
        TreeNode* rightLCA = findLCA(root->right, p, q);

        // If both left and right LCA are not null, it means one node is in the left subtree,
        // and the other is in the right subtree, making the current node the LCA.
        if (leftLCA != nullptr && rightLCA != nullptr) {
            return root;
        }

        // If only one LCA is found (either in left or right subtree), return it.
        return (leftLCA != nullptr) ? leftLCA : rightLCA;
    }

8. Calculate the Diameter of a Binary Tree:

Question: Calculate the diameter of a binary tree, which is the length of the longest path between two nodes.
Explanation: The diameter is not necessarily the path through the root.

    int diameter(TreeNode* root, int& result) {
        if (root == nullptr) {
            return 0;
        }

        // Calculate the heights of the left and right subtrees recursively.
        int leftHeight = diameter(root->left, result);
        int rightHeight = diameter(root->right, result);

        // Update the result with the maximum diameter encountered.
        result = std::max(result, leftHeight + rightHeight);

        // Return the height of the current subtree.
        return 1 + std::max(leftHeight, rightHeight);
    }

    int diameterOfBinaryTree(TreeNode* root) {
        int result = 0; // Initialize the result to 0.
        diameter(root, result);
        return result;
    }

In Part 1, we've established a solid foundation in binary tree concepts, exploring traversals, tree height, and finding the Lowest Common Ancestor (LCA). With these fundamentals in our arsenal, we're ready to ascend to the next level. In Part 2, we'll dive into more advanced topics, including balancing trees, tree construction from various representations, and tackling complex interview questions. Get ready for an exciting journey as we elevate our binary tree expertise in Part 2!
📣 We'd love to hear from you! Share your thoughts, questions, or any additional topics you'd like us to cover in the comments below. Your valuable views and feedback are essential in shaping our content and providing you with the information you find most useful. Let's engage in a conversation and continue learning together! 🚀