Advanced Tree Data Structures
1) Search in a Binary Search Tree (Easy)
Question
Given the root of a Binary Search Tree and an integer val, return the subtree rooted with the node that has value equal to val. If such node does not exist, return null.
Code
class Solution {
public:
TreeNode* searchBST(TreeNode* root, int val) {
if (root == nullptr || root->val == val) {
return root;
}
if(val < root->val){
return searchBST(root->left,val);
}
return searchBST(root->right,val);
}
};
OUTPUT:
Explanation
Binary Search Tree follows the property that left subtree contains smaller values and right subtree contains larger values.
We compare the given value with root value.
If equal, we return root.
If smaller, we search in left subtree.
If greater, we search in right subtree.
The recursion continues until the value is found or the node becomes null.
Time Complexity
O(h), where h is height of tree
Best case: O(log n)
Worst case: O(n)
Space Complexity
O(h) due to recursion stack
2) Convert Sorted Array to Binary Search Tree (Easy)
Question
Given an integer array nums sorted in ascending order, convert it to a height-balanced BST.
Code
class Solution {
public:
TreeNode* buildbalancedBST(vector<int>& nums,int l,int r){
if(l>r) return nullptr;
int mid = (l+r)/2;
TreeNode* node= new TreeNode(nums[mid]);
node->left=buildbalancedBST(nums,l,mid-1);
node->right=buildbalancedBST(nums,mid+1,r);
return node;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* newroot= buildbalancedBST(nums,0,nums.size()-1);
return newroot;
}
};
OUTPUT:
Explanation
Since array is sorted, middle element should become root to maintain balance.
Left half forms left subtree and right half forms right subtree.
This process is applied recursively until the subarray becomes empty.
Choosing middle ensures the tree remains height balanced.
Time Complexity
O(n) because each element is visited once
Space Complexity
O(log n) recursion stack (balanced tree)
3) Balanced Binary Tree (Easy)
Question
Determine if a binary tree is height-balanced.
Code
class Solution {
public:
int checkHeight(TreeNode* root) {
if (root == NULL)
return 0;
int leftHeight = checkHeight(root->left);
if (leftHeight == -1)
return -1;
int rightHeight = checkHeight(root->right);
if (rightHeight == -1)
return -1;
if (abs(leftHeight — rightHeight) > 1)
return -1;
return 1 + max(leftHeight, rightHeight);
}
bool isBalanced(TreeNode* root) {
return checkHeight(root) != -1;
}
};
OUTPUT:
Explanation
For each node, we calculate left and right subtree height.
If difference is more than 1, tree is not balanced.
We return -1 as a flag to indicate imbalance.
If any subtree returns -1, we directly propagate it upward.
Otherwise, we return height normally.
Time Complexity
O(n)
Space Complexity
O(h)
4) Path Sum (Easy)
Question
Return true if the tree has a root-to-leaf path such that adding all values equals targetSum.
Code
class Solution {
public:
bool hasPathSum(TreeNode* root, int targetSum) {
if (root == nullptr)
return false;
if (root->left == nullptr && root->right == nullptr) {
return targetSum == root->val;
}
int remainingSum = targetSum — root->val;
return hasPathSum(root->left, remainingSum) ||
hasPathSum(root->right, remainingSum);
}
};
OUTPUT:
Explanation
We subtract current node value from targetSum.
If we reach a leaf node and remaining sum equals node value, return true.
Otherwise, recursively check left and right subtrees.
If either subtree returns true, answer is true.
Time Complexity
O(n)
Space Complexity
O(h)
5) Insert into a Binary Search Tree (Medium)
Question
Insert a value into BST and return root.
Code
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(root==NULL){
return new TreeNode(val);
}
if(val<root->val){
root->left=insertIntoBST(root->left,val);
}
if(val>root->val){
root->right=insertIntoBST(root->right,val);
}
return root;
}
};
OUTPUT:
Explanation
If root is null, create new node.
If value is smaller, go left.
If larger, go right.
Recursively find correct position where child is null and insert.
BST property is maintained automatically.
Time Complexity
O(h)
Space Complexity
O(h)
6) Implement Trie (Prefix Tree) (Medium)
Question
Implement insert, search and startsWith operations in Trie.
Code
class TrieNode{
public:
bool isCompleteWord;
TrieNode* children[26];
TrieNode() {
isCompleteWord= false;
memset(children, 0 , sizeof(children));
}
};
Get Vashanth’s stories in your inbox
Join Medium for free to get updates from this writer.
class Trie {
public:
TrieNode* root;
Trie() {
root= new TrieNode();
}
void insert(string word) {
TrieNode* node= root;
for(char ch : word){
int idx= ch — ‘a’;
if(node->children[idx]==NULL) node->children[idx]= new TrieNode();
node= node->children[idx];
}
node->isCompleteWord=true;
}
bool search(string word) {
TrieNode* node= root;
for(char ch : word){
int idx= ch — ‘a’;
if(node->children[idx]==NULL) return false;
node= node->children[idx];
}
return node->isCompleteWord;
}
bool startsWith(string prefix) {
TrieNode* node= root;
for(char ch : prefix){
int idx= ch — ‘a’;
if(node->children[idx]==NULL) return false;
node= node->children[idx];
}
return true;
}
};
OUTPUT:
Explanation
Trie stores characters in tree form.
Each node has 26 children for lowercase letters.
Insert creates nodes if they do not exist.
Search checks full word and verifies end marker.
startsWith only checks prefix existence.
It is efficient for prefix-based searching.
Time Complexity
Insert: O(n)
Search: O(n)
Prefix: O(n)
Space Complexity
O(total characters inserted)
7) Validate Binary Search Tree (Medium)
Question
Given the root of a binary tree, determine if it is a valid Binary Search Tree (BST).
A Binary Search Tree must satisfy the following conditions:
- The left subtree of a node contains only nodes with values less than the node’s value.
- The right subtree of a node contains only nodes with values greater than the node’s value.
- Both the left and right subtrees must also be Binary Search Trees.
Return true if the tree is a valid BST, otherwise return false.
Code
class Solution {
public:
bool validate(TreeNode* node, long minVal, long maxVal) {
if (node == nullptr)
return true;
if (node->val <= minVal || node->val >= maxVal)
return false;
return validate(node->left, minVal, node->val) &&
validate(node->right, node->val, maxVal);
}
bool isValidBST(TreeNode* root) {
return validate(root, LONG_MIN, LONG_MAX);
}
};
OUTPUT:
Explanation
Each node must lie within a valid range.
Initially range is (-infinity, +infinity).
For left child, max becomes parent value.
For right child, min becomes parent value.
If any node violates range, tree is not valid BST.
Time Complexity
O(n)
Space Complexity
O(h)
8) Serialize and Deserialize Binary Tree (Hard)
Question
Design an algorithm to serialize and deserialize a binary tree.
Serialization is the process of converting a binary tree into a string so that it can be stored or transmitted.
Deserialization is the process of reconstructing the original binary tree from the serialized string.
You need to implement two functions:
- serialize(TreeNode* root)
- deserialize(string data)
The structure of the tree must remain exactly the same after deserialization.
Code
class Codec {
public:
string serialize(TreeNode* root) {
if(!root){
return “”;
}
string s=””;
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode* curNode = q.front();
q.pop();
if(curNode==NULL) s.append(“#,”);
else s.append(to_string(curNode->val)+’,’);
if(curNode!=NULL){
q.push(curNode->left);
q.push(curNode->right);
}
}
return s;
}
TreeNode* deserialize(string data) {
if(data.size()==0) return NULL;
stringstream s(data);
string str;
getline(s,str,’,’);
TreeNode *root = new TreeNode(stoi(str));
queue<TreeNode*> q;
q.push(root);
while(!q.empty()){
TreeNode *node=q.front();
q.pop();
getline(s,str,’,’);
if(str==”#”){
node->left=NULL;
}
else{
TreeNode* leftNode= new TreeNode(stoi(str));
node->left=leftNode;
q.push(leftNode);
}
getline(s,str,’,’);
if(str==”#”){
node->right=NULL;
}
else{
TreeNode* rightNode= new TreeNode(stoi(str));
node->right=rightNode;
q.push(rightNode);
}
}
return root;
}
};
OUTPUT:
Explanation
Serialization converts tree into string using level order traversal.
Null nodes are marked using “#”.
Deserialization reads values one by one and rebuilds tree using queue.
This ensures original structure is preserved.
Time Complexity
O(n)
Space Complexity
O(n)
9) Binary Tree Cameras (Hard)
Question
You are given the root of a binary tree.
Install cameras on nodes of the tree such that every node is monitored.
Each camera placed at a node can monitor:
- Its parent
- Itself
- Its immediate children
Return the minimum number of cameras needed to monitor all nodes of the tree.
Code
class Solution {
public:
int count=0;
int solve(TreeNode* root){
if(root==NULL){
return 1;
}
int l=solve(root->left);
int r=solve(root->right);
if(l==0 || r==0){
count++;
return 2;
}
if(l==2 || r==2){
return 1;
}
return 0;
}
int minCameraCover(TreeNode* root) {
if(solve(root)==0){
count++;
}
return count;
}
};
OUTPUT:
Explanation
Each node has three states:
0 = not covered
1 = covered
2 = has camera
If any child is not covered, place camera at current node.
If any child has camera, current node is covered.
If children are covered but no camera, current node is not covered.
Finally check root condition.
This greedy bottom-up approach ensures minimum cameras.
Time Complexity
O(n)
Space Complexity
O(h)
