Advanced Data Structures

Easy Programs:

1.Range Sum of BST

Given the root node of a binary search tree and two integers low and high, return the sum of values of all nodes with a value in the inclusive range [low, high].

Input: [1 2 -1 -1 3 -1 -1], low=1, high=3

Output: 4

Answer:

#include <iostream>
using namespace std;

struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int rangusum(Node* root, int low, int high) {
if (!root) return 0;
int sum = 0;

if (root->val >= low && root->val <= high) sum += root->val;

if (root->val > low) sum += rangesum(root->left, low, high);
if (root->val < high) sum += rangesum(root->right, low, high);

return sum;
}

Node* build() {
int val;
cin >> val;
if (val == -1) return nullptr;
Node* node = new Node(val);
node->left = build();
node->right = build();
return node;
}

int main() {
cout << "Enter tree nodes in preorder (-1 for null):\n";
Node* root = build();

int low, high;
cout << "Enter range low and high: ";
cin >> low >> high;

int sum = rangesum(root, low, high);
cout << "Sum of nodes in range [" << low << ", " << high << "] is: " << sum << endl;
return 0;
}

Output:

Explanation:

• Traverse the BST recursively.
• Add node value if it lies within [low, high].
• Skip left/right subtrees if values cannot fall in the range.

2.Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

Input: n=5, [-10 -3 0 5 9]

Output: 0 -10 null -3 null null 5 null 9 null null

Answer:

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

Node* sortedarraytoBST(int nums[], int left, int right) {
    if (left > right) return nullptr;
    int mid = left + (right - left) / 2;
    Node* root = new Node(nums[mid]);
    root->left = sortedarraytoBST(nums, left, mid - 1);
    root->right = sortedarraytoBST(nums, mid + 1, right);
    return root;
}

void print(Node* root) {
    if (!root) {
        cout << "null ";
        return;
    }
    cout << root->val << " ";
    print(root->left);
    print(root->right);
}

int main() {
    int n;
    cout << "Enter number of elements in sorted array: ";
    cin >> n;

    int nums[n];
    cout << "Enter elements in ascending order: ";
    for (int i = 0; i < n; i++) cin >> nums[i];

    Node* root = sortedarraytoBST(nums, 0, n - 1);

    cout << "BST output: ";
    print(root);
    cout << endl;

    return 0;
}

Output:

Explanation:

• Choose middle element as root to maintain height balance.
• Recursively build left subtree from left half of array, right subtree from right half.
• Ensures the resulting tree is a balanced BST.

3.Binary Tree Inorder Traversal

Given the root of a binary tree, return the inorder traversal of its nodes' values.

Input: [1 -1 2 3 -1 -1 -1]

Output: 1 3 2

Answer:

#include <iostream>
using namespace std;

struct Node {
    int val;
    Node* left;
    Node* right;
    Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

void inorder(Node* root) {
    if (!root) return;
    inorder(root->left);
    cout << root->val << " ";
    inorder(root->right);
}

Node* build() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    Node* node = new Node(val);
    node->left = build();
    node->right = build();
    return node;
}

int main() {
    cout << "Enter tree nodes in preorder (-1 for null):\n";
    TreeNode* root = build();

    cout << "Inorder traversal: ";
    inorder(root);
    cout << endl;

    return 0;
}

Output:

Explanation:

• Recursively visit left subtree → root → right subtree.
• Print node values in ascending order for BST.
• Base case: return when node is NULL.

4.Sum of Left Leaves

Given the root of a binary tree, return the sum of all left leaves.

A leaf is a node with no children. A left leaf is a leaf that is the left child of another node.

Input: [3 9 -1 -1 20 15 -1 -1 7 -1 -1]

Output: 24

Answer:

#include <iostream>
using namespace std;

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

int sumleft(Node* root, bool isLeft) {
    if (!root) return 0;

    if (!root->left && !root->right) {
        if (isLeft) return root->val;
        else return 0;
    }

    return sumleft(root->left, true) + sumleft(root->right, false);
}

int sumleft(Node* root) {
    return sumleft(root, false);
}

Node* build() {
    int val;
    cin >> val;
    if (val == -1) return nullptr;
    Node* node = new Node(val);
    node->left = build();
    node->right = build();
    return node;
}

int main() {
    cout << "Enter tree nodes in preorder (-1 for null):\n";
    Node* root = build();

    int sum = sumleft(root);
    cout << "Sum of left leaves: " << sum << endl;

    return 0;
}

Output:

Explanation:

• Traverse tree recursively while tracking whether a node is a left child.
• If node is a left leaf, add its value to sum.
• Return total sum after visiting all nodes.

Medium Programs:

1. Insert into a Binary Search Tree

You are given the root node of a binary search tree (BST) and a value to insert into the tree. Return the root node of the BST after the insertion. It is guaranteed that the new value does not exist in the original BST.

Notice: that there may exist multiple valid ways for the insertion, as long as the tree remains a BST after insertion. You can return any of them.

Input: [1 2 -1 -1 3 -1 -1] , Insert =4

Output: 2 1 3 4

Answer:

#include <iostream>
using namespace std;

struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(NULL), right(NULL) {}
};

Node* build() {
int val;
cin >> val;
if (val == -1) return NULL;

Node* root = new Node(val);
root->left = build();
root->right = build();
return root;
}

Node* insert(Node* root, int val) {
if (root == NULL)
return new Node(val);

if (val < root->val)
root->left = insert(root->left, val);
else
root->right = insert(root->right, val);

return root;
}

void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}

int main() {
cout << "Enter tree in preorder (-1 for NULL): ";
Node* root = build();

int val;
cout << "Enter value to insert: ";
cin >> val;

root = insert(root, val);

cout << "Inorder after insertion: ";
inorder(root);

return 0;
}

Output:

Explanation:

• Traverse BST recursively to find the correct position.
• Insert the new value as a leaf node.
• Maintain BST property after insertion.

2.Delete Node in a BST

Get Hariharanm’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.

Basically, the deletion can be divided into two stages:

1. Search for a node to remove.
2. If the node is found, delete the node.

Input: [6 2 6 7 8 -1 -1 -1 -1 -1 -1] ,Delete- 6

Output: 8 7 6 2

Answer:

#include <iostream>
using namespace std;

struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(NULL), right(NULL) {}
};

Node* build() {
int val;
cin >> val;
if (val == -1) return NULL;

Node* root = new Node(val);
root->left = build();
root->right = build();
return root;
}

Node* findmin(Node* root) {
while (root->left != NULL)
root = root->left;
return root;
}

Node* deletenode(Node* root, int key) {
if (!root) return NULL;

if (key < root->val)
root->left = deletenode(root->left, key);
else if (key > root->val)
root->right = deletenode(root->right, key);
else {
if (!root->left) {
Node* temp = root->right;
delete root;
return temp;
}
else if (!root->right) {
Node* temp = root->left;
delete root;
return temp;
}
Node* temp = findmin(root->right);
root->val = temp->val;
root->right = deletenode(root->right, temp->val);
}
return root;
}

void inorder(Node* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}

int main() {
cout << "Enter BST in preorder (-1 for NULL): ";
Node* root = build();

int key;
cout << "Enter key to delete: ";
cin >> key;

root = deletenode(root, key);

cout << "Inorder after deletion: ";
inorder(root);
return 0;
}

Output:

Explanation:

• Search for node with the key using BST property.
• Handle three cases: leaf, one child, two children (replace with inorder successor).
• Recursively update tree structure to preserve BST.

3.Validate Binary Search Tree

Given the root of a binary tree, determine if it is a valid binary search tree (BST).

A valid BST is defined as follows:

• The left subtree of a node contains only nodes with keys strictly less than the node’s key.
• The right subtree of a node contains only nodes with keys strictly greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Input:[ 5 2 -1 -1 7 -1 -1]

Output: Valid BST

Answer:

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

struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

bool isvalid(Node* node, long long minVal, long long maxVal) {
if (!node) return true;
if (node->val <= minVal || node->val >= maxVal) return false;
return isvalid(node->left, minVal, node->val) &&
isvalid(node->right, node->val, maxVal);
}

bool isvalid(Node* root) {
return isvalid(root, LLONG_MIN, LLONG_MAX);
}

Node* build() {
int val;
cin >> val;
if (val == -1) return nullptr;
Node* node = new Node(val);
node->left = build();
node->right = build();
return node;
}

int main() {
cout << "Enter tree nodes in preorder (-1 for null):\n";
Node* root = build();

if (isvalid(root))
cout << "The tree is a valid BST." << endl;
else
cout << "The tree is NOT a valid BST." << endl;

return 0;
}

Output:

Explanation:

• Recursively check each node value lies within valid min/max range.
• Update bounds for left and right subtrees while traversing.
• Return false if any node violates BST property.

Hard Programs:

1.Recover a Tree From Preorder Traversal

We run a preorder depth-first search (DFS) on the root of a binary tree.

At each node in this traversal, we output D dashes (where D is the depth of this node), then we output the value of this node. If the depth of a node is D, the depth of its immediate child is D + 1. The depth of the root node is 0.

If a node has only one child, that child is guaranteed to be the left child.

Given the output traversal of this traversal, recover the tree and return its root.

Input: [1 -2–3 — -4 -5–6 — -7]

Output: 1 2 5 3 null 6 null 4 null 7

Answer:

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

struct Node {
int val;
Node* left;
Node* right;
Node(int x) : val(x), left(nullptr), right(nullptr) {}
};

Node* build(const string& s, int& index, int depth) {
int n = s.size();
int i = index;
int dashCount = 0;

while (i < n && s[i] == '-') { dashCount++; i++; }
if (dashCount != depth) return nullptr;

int val = 0;
while (i < n && isdigit(s[i])) { val = val*10 + (s[i]-'0'); i++; }

Node* node = new Node(val);
index = i;

node->left = build(s, index, depth+1);
node->right = build(s, index, depth+1);

return node;
}

void deletet(Node* root) {
if (!root) return;
deletet(root->left);
deletet(root->right);
delete root;
}

void printLevelOrderTrim(TreeNode* root) {
if (!root) { cout << "[]\n"; return; }
queue<TreeNode*> q;
vector<string> arr;
q.push(root);

while (!q.empty()) {
TreeNode* node = q.front(); q.pop();
if (node) {
arr.push_back(to_string(node->val));
q.push(node->left);
q.push(node->right);
} else {
arr.push_back("null");
}
}

while (!arr.empty() && arr.back() == "null") arr.pop_back();

cout << "[";
for (size_t i = 0; i < arr.size(); i++) {
if (i > 0) cout << ",";
cout << arr[i];
}
cout << "]\n";
}

int main() {
string traversal;
cout << "Enter preorder traversal string (with '-' for depth): ";
getline(cin, traversal);

int index = 0;
TreeNode* root = buildTree(traversal, index, 0);

cout << "Tree in level-order format:\n";
printLevelOrderTrim(root);

deleteTree(root);
return 0;
}

Output:

Explanation:

• Parse preorder string using dashes to determine depth.
• Recursively attach left and right children according to depth.
• DFS ensures correct reconstruction of the original tree structure.

2.Maximum Sum BST in Binary Tree

Given a binary tree root, return the maximum sum of all keys of any sub-tree which is also a Binary Search Tree (BST).

Assume a BST is defined as follows:

• The left subtree of a node contains only nodes with keys less than the node’s key.
• The right subtree of a node contains only nodes with keys greater than the node’s key.
• Both the left and right subtrees must also be binary search trees.

Input: [3 4 5 8 6 3 -1 -1 -1 -1 -1 -1 -1]

Output: 17

Answer:

#include <iostream>
using namespace std;

struct Node {
int val;
Node* left;
Node* right;
Node(int v) : val(v), left(nullptr), right(nullptr) {}
};

int maxSum = 0;

int dfs(Node* node, int &minVal, int &maxVal) {
if (!node) {
minVal = INT_MAX;
maxVal = INT_MIN;
return 0;
}

int leftSum = dfs(node->left, minVal, maxVal);
int leftMin = minVal, leftMax = maxVal;
int rightSum = dfs(node->right, minVal, maxVal);
int rightMin = minVal, rightMax = maxVal;

if ((node->left && leftMax >= node->val) || (node->right && rightMin <= node->val))
return -1; 

int currSum = node->val + leftSum + rightSum;
maxSum = max(maxSum, currSum);

minVal = node->left ? leftMin : node->val;
maxVal = node->right ? rightMax : node->val;

return currSum;
}

int maxSumBST(Node* root) {
maxSum = 0;
int minVal, maxVal;
dfs(root, minVal, maxVal);
return maxSum;
}

Node* build() {
int val;
cin >> val;
if (val == -1) return nullptr;

Node* node = new Node(val);
node->left = build();
node->right = build();
return node;
}

int main() {
cout << "Enter tree nodes in preorder (-1 for null):\n";
Node* root = build();

cout << "Maximum sum BST in tree: " << maxSumBST(root) << endl;
return 0;
}

Output:

Explanation:

• Traverse tree post-order and check if each subtree is a BST.
• Compute sum of subtree if valid BST and update global max sum.
• Use min/max values to validate BST property for left and right subtrees.