🔥 Crack Easily Any Interview | Tree Data Structure Patterns With Questions

4358

Tree Data Structure Topics

✅ Tree (Binary Tree) Introduction
- Build TreeNode user define data structure
- Implement Binary Tree
✅ Tree Traversal techniques (Using Recursion, Stack & Morris Techniques)
- Inorder Traversal
- Preorder Traversal
- Postorder Traversal
- Level order Traversal
Ancestor problems
✅ Root to leaf path problems
✅ Depth problem
✅ Travel child to parent problems
Tree construction
Top, Bottom, Right, Left, Vertical & Diagonal View of binary tree
✅ Serialize and Deserialize tree
Node deletion
Distance between two Nodes
Binary Search Tree
✅ Validate Binary Tree & Binary Search Tree

Binary Tree Introduction

Binary Tree : Binary Tree is defined as a tree data structure where each node has at most 2 children. Since each element in a binary tree can have only 2 children, we typically name them the left and right child. Source : GFG

TreeNode Data Structure

// create TreeNode data structure
class TreeNode {
public:

    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) {
        this -> val = val;
        left = nullptr;
        right = nullptr;
    }

    TreeNode(int val, TreeNode* left, TreeNode* right) {
        this -> val = val;
        this -> left = left;
        this -> right = right;
    }
};

Implement Binary Tree

	/*
    Author: rushi_mungse
    Topic : Binary Tree Implementation

    Constructed binary tree is
                      1
                    /   \
                   /     \
                  2       3
                /  \      / \
               /    \    -1  -1
              /      \
             4        5
           /  \      /  \
          /    \    /    \
    -1(null)    -1 -1    -1

    input : 1 2 4 -1 -1 5 -1 -1 3 -1 -1
*/

#include <bits/stdc++.h>
using namespace std;

// create TreeNode data structure
class TreeNode {
public:

    int val;
    TreeNode* left;
    TreeNode* right;

    TreeNode(int val) {
        this -> val = val;
        left = nullptr;
        right = nullptr;
    }

    TreeNode(int val, TreeNode* left, TreeNode* right) {
        this -> val = val;
        this -> left = left;
        this -> right = right;
    }
};


TreeNode* implemetBT() {
    // user input for current node value
    int val; cin >> val;

    // if value is -1 then no more child for current tree node
    if(val == -1) return nullptr;

    // create new node
    TreeNode* node = new TreeNode(val);

    node -> left = implemetBT();
    node -> right = implemetBT();

    return node;
}

int main() {
    TreeNode* root = implemetBT();
    return 0;
}

Traversal Techniques

1.Inorder Traversal

/*
    Author: rushi_mungse
    Topic : Inorder Traversal

    Constructed Binary Tree
                      1
                    /   \
                   /     \
                  2       3
                /  \      / \
               /    \    -1  -1
              /      \
             4        5
           /  \      /  \
          /    \    /    \
    -1(null)    -1 -1    -1

    input: 1 2 4 -1 -1 5 -1 -1 3 -1 -1
    output: 4 2 5 1 3

*/

#include <bits/stdc++.h>
using namespace std;


// Write TreeNode data structure here -> see above code
// Write implemetBT function here -> see above code

void inOrderTraversal(TreeNode* root) {
    // if root node is null then return
    if(!root) return;

    inOrderTraversal(root -> left);
	// Do logic here
    cout << root -> val << " ";          
    inOrderTraversal(root -> right);

    return;
}


void inOrderTraversalUsingStack(TreeNode* root) {
    if(!root) return;

    stack<TreeNode*> st;
    TreeNode* cur = root;

    while(cur || !st.empty()) {
        while(cur) {
            st.push(cur);
            cur = cur -> left;
        }

        cur = st.top(); st.pop();
        cout << cur -> val << " ";
        cur = cur -> right;
    }

    return;
}


void inOrderMorrisTraversal(TreeNode* root) {
    if(!root) return;

    TreeNode *cur, *pre;
    cur = root;

    while(cur) {
        if(cur -> left == nullptr) {
            cout << cur -> val << " ";
            cur = cur -> right;
        }else {
            pre = cur -> left;
            while(pre -> right != nullptr && pre -> right != cur) {
                pre = pre -> right;
            }

            if(pre -> right == nullptr) {
                pre -> right = cur;
                cur = cur -> left;
            }else {
                pre -> right = nullptr;
                cout << cur -> val << " ";
                cur = cur -> right;
            }
        }
    }
    return;
}


int main() {
    // Call here implemetBT() -> function implemented above
    TreeNode* root = implemetBT();
    // inOrderTraversal(root);                        // Using recursion
    // inOrderTraversalUsingStack(root);              // Using stack
    inOrderMorrisTraversal(root);                     // Using morris traversal
    return 0;
}

2.Preorder Traversal

/*
    Author: rushi_mungse
    Topic : Preorder Traversal

    Constructed binary tree is
                      1
                    /   \
                   /     \
                  2       3
                /  \      / \
               /    \    -1  -1
              /      \
             4        5
           /  \      /  \
          /    \    /    \
    -1(null)    -1 -1    -1

    input : 1 2 4 -1 -1 5 -1 -1 3 -1 -1
    output : 1 2 4 5 3

*/

#include <bits/stdc++.h>
using namespace std;


// write TreeNode data structure here -> see above code
// write implemetBT function here -> see above code

void preOrderTraversal(TreeNode* root) {
    // if root node is null then return
    if(!root) return;

	// Do logic here
    cout << root -> val << " ";
    preOrderTraversal(root -> left);
    preOrderTraversal(root -> right);

    return;
}


void preOrderTraversalUsingStack(TreeNode* root) {
    if(!root) return;

    stack<TreeNode*> st;
    TreeNode* cur = root;

    while(cur || !st.empty()) {
        while(cur) {
            cout << cur -> val << " ";
            st.push(cur);
            cur = cur -> left;
        }

        cur = st.top(); st.pop();
        cur = cur -> right;
    }
}


void preOrderMorrisTraversal(TreeNode* root) {
    if(!root) return;

    TreeNode *cur, *pre;
    cur = root;

    while(cur) {
        if(cur -> left == nullptr) {
            cout << cur -> val << " ";
            cur = cur -> right;
        }else {
            pre = cur -> left;
            while(pre -> right != nullptr && pre -> right != cur) {
                pre = pre -> right;
            }

            if(pre -> right == nullptr) {
                cout << cur -> val << " ";
                pre -> right = cur;
                cur = cur -> left;
            }else {
                pre -> right = nullptr;
                cur = cur -> right;
            }
        }
    }
    return;
}


int main() {
    // implemetBT() -> function implemented above
    TreeNode* root = implemetBT();
    // preOrderTraversal(root);
    // preOrderTraversalUsingStack(root);
    preOrderMorrisTraversal(root);
    return 0;
}

3.Postorder Traversal

/*
    Author: rushi_mungse
    Topic : Postorder Traversal

    Constructed binary tree is
                      1
                    /   \
                   /     \
                  2       3
                /  \      / \
               /    \    -1  -1
              /      \
             4        5
           /  \      /  \
          /    \    /    \
    -1(null)    -1 -1    -1

    input :- 1 2 4 -1 -1 5 -1 -1 3 -1 -1
    output : 4 5 2 3 1

*/

#include <bits/stdc++.h>
using namespace std;


// write TreeNode data structure here -> see above code
// write implemetBT function here -> see above code

void postOrderTraversal(TreeNode* root) {
    // if root node is null then return
    if(!root) return;

    postOrderTraversal(root -> left);
    postOrderTraversal(root -> right);
    cout << root -> val << " ";           // main difference here

    return;
}


void postOrderTraversalUsingStack(TreeNode* root) {
    if(!root) return;

    stack<TreeNode*> st1, st2;
    st1.push(root);

    while(!st1.empty()) {
        TreeNode* top = st1.top(); st1.pop();
        st2.push(top);

        if(top -> left) st1.push(top -> left);
        if(top -> right) st1.push(top -> right);
    }

    while(!st2.empty()) {
        cout << st2.top() -> val << " ";
        st2.pop();
    }

    return;
}




int main() {
    // implemetBT() -> function implemented above
    TreeNode* root = implemetBT();
    // postOrderTraversal(root);
    postOrderTraversalUsingStack(root);
    return 0;
}

4.Level Order Traversal

/*
    Author: rushi_mungse
    Topic : Level Order Traversal

    Constructed binary tree is
                      1
                    /   \
                   /     \
                  2       3
                /  \      / \
               /    \    -1  -1
              /      \
             4        5
           /  \      /  \
          /    \    /    \
    -1(null)    -1 -1    -1

    input : 1 2 4 -1 -1 5 -1 -1 3 -1 -1
    output : 1
             2 3
             4 5
*/

#include <bits/stdc++.h>
using namespace std;


// write TreeNode data structure here -> see above code
// write implemetBT function here -> see above code

void levelOrderTraversal(TreeNode* root) {
    if(!root) return;
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()) {
        for(int sz = q.size(); sz > 0; sz--) {
            TreeNode* front = q.front(); q.pop();
            cout << front -> val << " ";
            if(front -> left) q.push(front -> left);
            if(front -> right) q.push(front -> right);
        }
        cout << endl;
    }
}

vector<vector<int>> levels;
void levelOrderTraversalUsingRecursion(TreeNode* root, int level) {
    if(!root) return;
    if(levels.size() >= level) levels.push_back({});
    levels[level].push_back(root -> val);

    levelOrderTraversalUsingRecursion(root -> left, level + 1);
    levelOrderTraversalUsingRecursion(root -> right, level + 1);
}


int main() {
    // implemetBT -> function implemented above
    TreeNode* root = implemetBT();
    // levelOrderTraversal(root);
    levelOrderTraversalUsingRecursion(root, 0);
    for(auto &l : levels) {
        for(auto &val : l) cout << val << " ";
        cout << endl;
    }
    return 0;
}

Depth Problems

Depth of node : The depth of a node in a binary tree is the total number of edges from the root node to the that node.

Clalculate depth of given node value

bool findDepth(TreeNode* root, int target, int depth) {
	// Return false means we don't meet target node yet
	if(!root) return false;
	// return true and save depth of that node in ans and return true
	if(root -> val == target) {
		ans = depth;
		return true;
	}
	// if we meet the target then not go further just return true
	if(findDepth(root -> left, target, depth + 1)) return true;
	if(findDepth(root -> right, target, depth + 1)) return true;
	
	return false;
}

Quetions :
1.https://leetcode.com/problems/maximum-depth-of-binary-tree/
2.https://leetcode.com/problems/minimum-depth-of-binary-tree/
3.https://leetcode.com/problems/minimum-absolute-difference-in-bst/
4.https://leetcode.com/problems/maximum-depth-of-n-ary-tree/

Travel child to parent problems (Radial Traversal)

In such type of problem we given target node [any node in tree also possibly root] and travel level by level from that node to finding ans.

Template

Build parent and child relation map
Do level order traversal or DFS

// Building parent and child relation map
unordered_map<TreeNode*, TreeNode*> parent;
void dfs(TreeNode* root, TreeNode* par) {
	if(!root) return;
	parent[root] = par;
	dfs(root -> left, root);
	dfs(root -> right, root);
}

// Do level order traversal
void levelOrderTraversal(TreeNode* target, int data) {
	queue<TreeNode*> q;
	q.push(target);
	
	vector<bool> seen(N);
	seen[target -> val] = true;
	
	while(!q.empty()) {
		for(int sz = q.size(); sz > 0; sz--) {
			TreeNode* cur = q.front(); q.pop();
			// push left child
			if(cur -> left && !seen[cur -> left -> val]) {
				seen[cur -> left -> val] = true;
				q.push(cur -> left);
			}
			// push right child
			if(cur -> right && !seen[cur -> right -> val]) {
				seen[cur -> right -> val] = true;
				q.push(cur -> right);
			}
			// push parent also
			if(parent[cur] && !seen[parent[cur] -> val]) {
				seen[parent[cur] -> val] = true;
				q.push(parent[cur])
			}
		}
	}
}

863. All Nodes Distance K in Binary Tree

class Solution {
    unordered_map<TreeNode*, TreeNode*> parent;
    vector<int> ret;

    void dfs(TreeNode* root, TreeNode* par) {
		if(!root) return;
		parent[root] = par;
		dfs(root -> left);
		dfs(root -> right);
    }

    void levelOrder(TreeNode* target, int k) {
        vector<bool> seen(501);
        seen[target -> val] = true;

        queue<TreeNode*> q;
        q.push(target);

        while(!q.empty() && k--) {
            for(int sz = q.size(); sz > 0; sz--) {
                TreeNode* cur = q.front(); q.pop();
                if(cur -> left && !seen[cur -> left -> val]) {
                    q.push(cur -> left);
                    seen[cur -> left -> val] = 1;
                }
                if(cur -> right && !seen[cur -> right -> val]) {
                    q.push(cur -> right);
                    seen[cur -> right -> val] = 1;
                }
                if(parent[cur] && !seen[parent[cur] -> val]) {
                    q.push(parent[cur]);
                    seen[parent[cur] -> val] = 1;
                }
            }
        }

        while(!q.empty()) {
            ret.push_back(q.front() -> val);
            q.pop();
        }
    }
public:
    vector<int> distanceK(TreeNode* root, TreeNode* target, int k) {
        if(!root) return ret;
        dfs(root, nullptr);
        levelOrder(target, k);
        return ret;
    }
};

Root to leaf path problems

Root to Leaf : In such type of problem we need to calculate optimal ans at all leaf nodes.

Template

Travers root to leaf at the leaf node return what ever in question says.

    int solve(TreeNode* root) {
		// This node is not a leaf node so that case just return any ans that not effect on final ans
		// ex. we calculate max sum root to leaf then that case return INT_MIN
        if(!root) return 0; 
		
		// do logic here ...
		
		// This is a leaf node, it has no left and right child. return ans
        if(!root -> left && !root -> right) return sum;
		
        int left = sumRootToLeaf(root -> left); // left call
        int right = sumRootToLeaf(root -> right); // right call
		
		// return what ever question says
        return max(left, right);
    }

1022. Sum of Root To Leaf Binary Number

class Solution {
public:
    int sumRootToLeaf(TreeNode* root, int tot = 0) {
        if(!root) return 0;  
        tot <<= 1;
        if(root -> val) tot |= 1;
        if(!root -> left && !root -> right) return tot;
        int left = sumRootToLeaf(root -> left, tot);
        int right = sumRootToLeaf(root -> right, tot);
        return left + right;
    }
}

Serialize and Deserialize tree

Serialize : Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Deserialize : Reconstruct the tree from serailize sequence data(string)

Serialize binary tree : In that case we converting binary structure or object into string using preorder.(encode)

string serialize(TreeNode* root) {
	// if current node is null then return "N" -> it's indicates this node is null node it's useful to   
	// deserialize tree
	if(!root) return "N";
	// we use seperator ',' for separate nodes
	return to_string(root -> val) + "," + serialize(root -> left) + "," + serialize(root -> right);
}

// input formate : [ node, "N", node, node, "N", "N"]

Deserialize binary tree : converting string to binary tree using preorder (decode)

    TreeNode* deserialize(int &i, string s) {
		// if current node 'N' then reuturn nullptr
        if(s[i] == 'N') { 
            i += 2; 
            return nullptr; 
        }
		// calculate value
        string val = "";
        while(s[i] != ',') val.push_back(s[i++]); 
        i++;

        if(val.empty()) return nullptr;
        
        TreeNode* root = new TreeNode(stoi(val));
        root -> left = deserialize(i, s);
        root -> right = deserialize(i, s);
		
        return root;
    }

Validate Trees

1361. Validate Binary Tree Nodes

Valid Binary Tree : One node has two child node without forming a cycle.
Algorithm :
- Build tree
- Find out root node (indegree of root node is 0)
- Check cycle present in tree and also check connected components == 1

class Node {
public : 
		Node *left, *right;
		int val;
  	Node(int val) {
			this -> val = val;
			left = nullptr;
			right = nullptr;
		}
};

class Solution {
public : 
	bool validateBinaryTreeNodes(int n, vector<int>& leftChild, vector<int>& rightChild) {
		// build tree using left child and right child
		vector<Node*> tree(n);
		vector<int> inDeg(n);
		for(int i = 0; i < n; i++) tree[i] = new Node(i);
		for(int i = 0; i < n; i++) {
			// if left child already present then 
			if((leftChild[i] != -1 && tree[i] -> left) || (rightChild[i] != -1 && tree[i] -> right)) 
				return false;
			if(leftChild[i] != -1) {
				tree[i] -> left = tree[leftChild[i]];
				inDeg[leftChild[i]]++;
			}
			if(rightChild[i] != -1) {
				tree[i] -> right = tree[rightChild[i]];
				inDeg[rightChild[i]]++;
			}
      }
			
		int rootNode = -1;
		for(int i = 0; i < n; i++) {
			if(inDeg[i] == 0) {
				if(rootNode != -1) return false;
				rootNode = i;
			}
		}
		if(rootNode == -1) return false;
		vector<bool> visited(n);
		return isCyclePresent(rootNode, tree,visited) && !count(visited.begin(), visited.end(), false);
	}

		bool isCyclePresent(int node, vector<Node*> &tree, vector<bool>& visited) {
			visited[node] = true;
			if(tree[node] -> left && (visited[tree[node] -> left -> val] || !isCyclePresent(tree[node] -> left -> val, tree, visited))) return false;
			if(tree[node] -> right && (visited[tree[node] -> right -> val] ||!isCyclePresent(tree[node] -> right -> val, tree, visited))) return false;
			return true;
		}
};

98. Validate Binary Search Tree

BST MOST IMP PROPERTY BST inorder traversal is accending order.
using above property we validate bst easily.

🙏 More topics comming soon...

------------------------- If you helpful this artical, please upvote ------------------------------

Comments (3)