Solving BT and BST Coding Problems

Binary Tree and Binary Search Tree coding problem list

Photo by TamtArt on Unsplash

Problem List

1. Search in a binary search tree Easy
2. Insert a node in a binary search tree Easy
3. Convert Sorted Array to Binary Search Tree, video Easy
4. Height of binary tree Easy (Not implemented yet)
5. Symmetric tree Easy (Not implemented yet)
6. Merge two binary trees Medium
7. Is this a binary search tree? Leetcode Medium
8. Print left view of binary tree Medium(Not implemented yet)
9. Convert sorted array to binary search tree (Not implemented yet)
10. Binary tree inorder traversal with iterative method Medium (Not implemented yet)
11. Kth smallest element in a BST Leetcode Medium (Not implemented yet)

Representation in C++

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

C++ implementations

• Search in a binary search tree Easy

TreeNode* searchBST(TreeNode* root, int val) {
    if (!root) return NULL;
    if (val == root->val)
        return root;
    return (val < root->val)? searchBST(root->left, val): searchBST(root->right, val);
}

Explanation

1. Use recursion. The base case is the node is empty or the value is found.
2. Time complexity is O(log n) (n is the number of nodes).

• Insert a node in a binary search tree

Node* getNewNode(int data){
    Node* node = new Node(data);
    node->left = node->right = NULL;
    return node;
}
Node* insert(Node* root, int data){
    if (!root)//traverse till find an empty node, create a new one
        root = getNewNode(data);
    else if (root->data > data){ //insert in left subtree
        root->left = insert(root->left, data);
    }
    else root->right = insert(root->right, data); //insert in right subtree
    return root;
}

Explanation

1. If there is no node in a given BST then insert a new node as its Root Node.
2. Find the Node in a given Binary Search Tree where we need to insert the node ( as either left or a right child ). To find so, just compare the value with the root node’s value.
3. If the value is greater than the root node’s value — traverse down the root node in its right node and Go to Step 2 by considering this right node as the root node (Note: if there is no right node straight go to Step 3)
4. if the value is lesser than the root node’s value — traverse down the root node in its left node and Go to Step 2 by considering this left node as the root node (Note: if there is no left node straight go to Step 3)
5. Once an empty node is found, use step 1 to create a new node.
6. The run time complexity of insert operation using recursive way is O(height of a Binary Search Tree) i.e O(h) [worst-case], it can be O(n) if the tree is unbalanced or O(log n) if the tree is balanced.

• Convert Sorted Array to Binary Search Tree

TreeNode* insert(vector<int>& nums, int start, int end){
    if(start > end)
        return nullptr;
    int mid = (start+end)/2;
    TreeNode *node = new TreeNode(nums[mid]);
    node->left = insert(nums, start, mid-1);
    node->right = insert(nums, mid+1, end);
    return node;
}
TreeNode* sortedArrayToBST(vector<int>& nums){
    return insert(nums, 0, nums.size()-1); 
}

Explanation

1. T: O(n), S: O(logn)
2. Init start = 0, end = size-1 of the vector;
3. mid = (start+end)/2;
4. Create a tree node with mid as root (call it A)
5. Recursively do the following steps:
6. Calculate mid of left subarray and make it the root of left subtree of A
7. Calculate mid of right subarray and make it the root of right subtree of A

• Merge two binary trees

TreeNode* mergeTrees(TreeNode* t1, TreeNode* t2) {
    if (!t1)
        return t2;
    if (!t2)
        return t1;
    TreeNode *node = new TreeNode(t1->val + t2->val);
    node->left = mergeTrees(t1->left, t2->left);
    node->right = mergeTrees(t1->right, t2->right);
    return node;
}

Explanation

1. Use recursion, base case is when either or both of the node is null.
2. Consider there are only two nodes in each tree as a simple case.
3. Sub problem: New node’s left child is the result of mergeTree of the left children of both nodes.
4. This problem can be solved in place. e.g.

t1->val += t2->val;
TreeNode* leftsub = mergeTrees(t1->left, t2->left);
TreeNode* rightsub = mergeTrees(t1->right, t2->right);
t1->left = leftsub;
t1->right = rightsub;
return t1;

• Is this a binary search tree? Medium

bool check(Node* root, int min, int max){
    if (!root) return true;
    return (root->data > min && root->data < max &&
            check(root->left, min, root->data) &&
            check(root->right, root->data, max));
}
bool checkBST(Node* root) {
    return check(root, INT_MIN, INT_MAX);
}

Explanation

1. Not a perfect solution as a single node with the value INT_MIN or INT_MAX will fail.
2. An empty tree is BST.
3. Looks at each node only once.
4. Write a utility helper function that traverses down the tree keeping track of the narrowing min and max allowed values as it goes, looking at each node only once. The initial values for min and max should be INT_MIN and INT_MAX — they narrow from there
5. Time complexity is O(n), space O(n).