Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Sample Example
4.
Binary Tree
5.
Binary Search Tree
6.
Balanced Binary Search Tree
7.
Tree Traversal
8.
Solution Approach
9.
Algorithm
10.
Implementation
10.1.
Implementation in Java
10.2.
Output
10.3.
Implementation in C++
10.4.
Output
10.5.
Implementation in Python
10.6.
Output
11.
Complexity Analysis
11.1.
Time Complexity 
11.2.
Space Complexity
12.
Frequently Asked Questions
12.1.
What is a binary tree?
12.2.
What is a binary tree used for?
12.3.
What are binary search trees?
12.4.
What is tree traversal?
12.5.
What is post-order traversal?
13.
Conclusion
Last Updated: Mar 27, 2024
Medium

Check if Binary Tree Contains a Balanced BST of Size K

Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction

Hey, Ninja! Did you know a binary tree is one of the most widely used data structures for storing and organizing data? A balanced binary search tree (BST) is a special binary tree that follows certain rules to ensure optimal performance when searching for elements. With their unique property of maintaining a balanced height, BSTs allow faster search, insert, and delete operations.

check if the binary tree contains a balanced BST of size k

In this article, we'll discuss a problem that involves determining if a binary tree contains a balanced BST of size k. Through this article, you will understand the concept of binary trees, balanced BSTs, and how to check if a binary tree contains a balanced BST of size k.

Problem Statement

Given a binary tree, check if it contains at least one balanced BST of size k. If you find one, print yes; otherwise, print no. “k” is a positive integer and is given in the input. 

Note: Size k means there should be k nodes in the BST.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Sample Example

Consider the following binary tree:

example

Input: k = 3.

Output: Yes

Explanation: 

example

The tree here is itself a BST. We can find a BST of size three here, which is the left subtree of the root. It is also balanced. 

Now that we understand the problem let's move further to learn about its solution. But before that, we'll review some concepts we will use to solve this problem.

Let us build on the momentum with a brief discussion about binary trees.

Binary Tree

It is a hierarchical data structure consisting of nodes and edges, where each node has at most two children. The two children of a node are referred to as its left and right children. The node at the top of the binary tree is commonly known as the root. The nodes with no children are called leaves. To learn more, follow this article

Now, let’s see what’s a binary search tree.

Binary Search Tree

Binary search trees are based on the binary tree data structure and store data in a way that allows for fast search, insertion, and deletion operations. In a BST, each node has at most two child nodes, the left child and the right child. For any node in the tree, all elements in its left subtree are lesser than the node's key, and all elements in its right subtree are greater than the node's key.

In the given problem, we are supposed to look for a balanced binary tree. Let’s see what a balanced binary search tree is, exactly.

Balanced Binary Search Tree

balanced binary search tree is a type of binary search tree. In this, the heights of the left and right subtrees of every node differ by no more than one. The height of a binary tree is nothing but the number of edges from the root node to the farthest leaf.

Balanced binary search trees have several advantages over unbalanced ones. For example, they ensure that search, insert, and delete operations have a guaranteed time complexity of O(log n), where n indicates the number of nodes in the tree. This makes balanced binary search trees ideal for applications that require fast access to data.

Now, to find the triplet with a given sum, we first need to access each node of the BST. For this, you need to know about tree traversals. Let us discuss them briefly.

Tree Traversal

Tree traversal refers to visiting all the nodes in a tree data structure in a specific order. 
Consider the following BST to visualize the tree traversals we will discuss further.

example BST

There are three common ways to traverse a BST:

In-order traversal: In an in-order traversal of a BST, we visit the nodes in the order of increasing values. First, we explore the left subtree, after that, the root node, and at last, the right subtree. The result of an in-order traversal of a BST will be a sequence of its elements sorted in ascending order. 
 

An in-order traversal of the BST in the example is:

in order traversal

Pre-order traversal: In a pre-order traversal of a BST, we visit the root node first, followed by the nodes in the left subtree, and then the nodes in the right subtree.

Pre-order traversal of the BST in the example is:

pre order traversal

Post-order traversal: In a post-order traversal of a BST, we visit the nodes in the reverse order of a pre-order traversal. First, we explore the nodes in the left subtree, after that, the nodes in the right subtree, and finally, the root node.

Post-order traversal of the BST in the example is:

post order traversal

All these traversal methods visit the nodes in a different order, but they all allow us to process every node in the BST.
 

Now think about which of these traversals will be best suited for our question here.

You’re right; the post-order traversal will be most suited for this problem because we will try to go through the tree from bottom to top. By reading this article, you can learn how to do post-order traversal on a BST.
 

Now that our basics are brushed-up. Let's learn about the approach we’ll use to solve this problem.

Solution Approach

We will use the following approach to find a balanced BST of size k.

  • Use post-order traversal to visit each node in the tree.
     
  • At each node, check if the value of the node follows the properties of a binary search tree, i.e., if the value of the node is greater than the maximum value in its left subtree and lesser than the minimum value in its right subtree.
     
  • If the node follows the properties of a binary search tree, then check if the height difference between its left and right subtree is 0 or 1. If the height difference is 0 or 1, then the node is part of a balanced BST.

    The height of a tree can be calculated recursively by finding the maximum height of its left and right subtrees and adding 1 to it. The height of an empty tree is 0.
     
  • Check the size of the balanced BST rooted at the current node. If the size equals k, we have found a balanced BST of size k.
     
  • Repeat the process for all nodes in the tree.
     

Let’s now look at the algorithm to code this approach.

Algorithm

Following is the algorithm we will use to check if the binary tree contains a BST of size k.

  1. Define a class SubtreeData to store information about a subtree. The class contains the following attributes:

    1. validBST: Boolean flag indicating if the subtree is a valid BST or not.
       
    2. validBalancedTree: Boolean flag indicating if the subtree is balanced or not.
       
    3. treeSize: Integer value indicating the size of the subtree.
       
    4. treeHeight: Integer value indicating the height of the subtree.
       
    5. minVal: Integer value indicating the minimum value in the subtree.
       
    6. maxVal: Integer value indicating the maximum value in the subtree.
       
  2. Define a helper function helperFunctionBalancedBST to find a balanced BST of size k rooted at 'root.' The function takes three arguments:

    1. root: Pointer to the root node of the subtree being checked.
       
    2. k: Integer value indicating the size of the balanced BST being searched for.
       
    3. found: Boolean flag indicating if a balanced BST of size k has been found or not.
       
  3. The helper function has the following base case:

    1. If the root is Null, return a SubtreeData object representing an empty subtree.
      In this case, a SubtreeData object is returned with values of validBST(true), validBalancedTree(true), treeSize(0), treeHeight (0), minVal(INT_MIN), and maxVal (INT_MAX).
       
  4. Recursively check the left and right subtrees using the helper function, storing their SubtreeData objects in leftSubtree and rightSubtree, respectively.
     
  5. If a balanced BST of size k has already been found, return an empty SubtreeData object.
     
  6. Check if the current subtree is a valid BST by verifying that both the left and right subtrees are valid BSTs and that the minimum and maximum values of the left and right subtrees do not violate the ordering of the root node. 

    If the subtree is not a valid BST, return a SubtreeData object with values indicating an invalid BST.

    In this case, a SubtreeData object is returned with values of validBST(false), validBalancedTree(false), treeSize(0), treeHeight (0), minVal(0), and maxVal (0).
     
  7. Check if the current subtree is a balanced tree by verifying that the absolute difference between the heights of the left and right subtrees is at most 1. Store the boolean result in the variable validBalancedTree.
     
  8. Compute the SubtreeData object for the current subtree by setting its values based on the values of the left and right subtrees and the root node. 

    1. Set the validBST value to true. This is because we have already dealt with the case of an invalid BST. If we reach here, the subtree is a valid BST.
       
    2. The value of validBalancedTree value to the value computed in step 7.
       
    3. The treeSize value to 1 plus the sizes of the left and right subtrees.
       
  9. The treeHeight value to 1 plus the maximum height of the left and right subtrees.
     
  10. The minVal to the minimum value of the left subtree or the value of the root node if there is no left subtree.
     
  11. The maxVal to the maximum value of the right subtree or the value of the root node if there is no right subtree.
     
  12. The current subtree is a balanced BST of size k if the treeSize = k and validBalancedTree = True. In this case, set the found variable to true.
     
  13. Return the SubtreeData object for the current subtree.
     
  14. Define a function check that takes in a TreeNode pointer 'root' and an integer 'k,' representing the desired size of the balanced BST.
     
  15. In the check function, set the found variable to false and call the helper function helperFunctionBalancedBST with the parameters 'root', 'k,' and 'found.'
     
  16. If a balanced BST of size k was found, return 1; otherwise, return 0.
     
  17. If the check function returns true, print, "Balanced BST of size k exists." Otherwise, print, " Balanced BST of size k doesn’t exist."
     

Let us now look at the implementation of this algorithm.

Implementation

Following is the implementation of the above-discussed approach in Java, C++, and Python.

Implementation in Java

import java.util.*;

// A binary tree node
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
}

// Class to store information about a subtree
class SubtreeData {
    boolean validBST;
    boolean validBalancedTree;
    int treeSize;
    int treeHeight;
    int minVal;
    int maxVal;
    
    public SubtreeData(boolean validBST, boolean validBalancedTree, int treeSize, int treeHeight, int minVal, int maxVal) {
        this.validBST = validBST;
        this.validBalancedTree = validBalancedTree;
        this.treeSize = treeSize;
        this.treeHeight = treeHeight;
        this.minVal = minVal;
        this.maxVal = maxVal;
    }
}

public class Main {


    // Function to create a tree node
    static TreeNode makeTree(int value) {
        TreeNode temp = new TreeNode();
        temp.left = temp.right = null;
        temp.val = value;
        return temp;
    }

    /* 
        Helper function to find
        a balanced BST of treeSize k. It 
        returns information about the 
        subtree rooted at 'root'
    */
    static SubtreeData helperFunctionBalancedBST(TreeNode root, int k, boolean[] found) {
        
        // Base case: empty subtree
        if (root == null) {
            return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        /*
            Recursively check the 
            left and right subtrees
        */
        SubtreeData leftSubtree = helperFunctionBalancedBST(root.left, k, found);
        if (found[0]) {
            return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }


        SubtreeData rightSubtree = helperFunctionBalancedBST(root.right, k, found);
        if (found[0]) {
            return new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        }

        /*
            Check if the current 
            subtree is a valid BST
        */
        if (!leftSubtree.validBST || !rightSubtree.validBST ||
                (root.left != null && leftSubtree.maxVal > root.val) ||
                (root.right != null && rightSubtree.minVal < root.val)) {
            return new SubtreeData(false, false, 0, 0, 0, 0);
        }

         /*
            Check if the current 
            subtree is balanced
         */
        boolean validBalancedTree = (Math.abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1);

        // Compute the information for the current subtree
        SubtreeData currentSubtree = new SubtreeData(true, true, 0, 0, Integer.MAX_VALUE, Integer.MIN_VALUE);
        currentSubtree.validBST = true;
        currentSubtree.validBalancedTree = validBalancedTree;
        currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize;
        currentSubtree.treeHeight = Math.max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1;

        // Finding currentSubtree.minVal
        if (root.left != null) {
            currentSubtree.minVal = leftSubtree.minVal;
        } else {
            currentSubtree.minVal = root.val;
        }
        
        // Finding currentSubtree.mixVal
        if (root.right != null) {
            currentSubtree.maxVal = rightSubtree.maxVal;
        } else {
            currentSubtree.maxVal = root.val;
        }

        /*
            If the current subtree is 
            a balanced BST of treeSize k, 
            we're done!
        */
        if (validBalancedTree && currentSubtree.treeSize == k) {
            found[0] = true;
        }

        /*
            Return the information 
            for the current subtree
        */
        return currentSubtree;
    }

    /*
        Finds a balanced BST of 
        Size k rooted at 'root'
    */
    static int check(TreeNode root, int k) {
        boolean[] found = new boolean[1];
        SubtreeData result = helperFunctionBalancedBST(root, k, found);
        if (found[0]) {
            return 1;
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
        TreeNode root = makeTree(4);
        root.left = makeTree(2);
        root.right = makeTree(5);
        root.left.left = makeTree(1);
        root.left.right = makeTree(3);
        root.right.right = makeTree(6);
        int k = 3;

        int balancedBST = check(root, k);
        if (balancedBST == 1) {
            System.out.println("Balanced BST of size k exists");
        } else {
            System.out.println("Balanced BST of size k doesn't exist");
        }
    }
}

Output

output

Implementation in C++

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

// A binary tree node
struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
};

// Structure to store information about a subtree
struct SubtreeData {
    bool validBST;     
    bool validBalancedTree;
    int treeSize;      
    int treeHeight;     
    int minVal;     
    int maxVal;     
};

// Function to create a tree node
TreeNode* makeTree(int value) {
    TreeNode* temp = new TreeNode();
    temp->left = temp->right= NULL;
    temp->val = value;
    return temp;
}

/* 
    Helper function to find
    a balanced BST of treeSize k. It 
    returns information about the 
    subtree rooted at 'root'
*/
SubtreeData helperFunctionBalancedBST(TreeNode* root, int k, bool &found) {
    
    // Base case: empty subtree
    if (root == NULL) {
        return { true, true, 0, 0, INT_MAX, INT_MIN };
    }

    /*
        Recursively check the 
        left and right subtrees
    */
    SubtreeData leftSubtree = helperFunctionBalancedBST(root->left, k, found);
    if (found) {
        return {}; 
    }
    
    SubtreeData rightSubtree = helperFunctionBalancedBST(root->right, k, found);
    if (found) {
        return {};
    }

    /*
        Check if the current 
        subtree is a valid BST
    */
    if (!leftSubtree.validBST || !rightSubtree.validBST ||
            (root->left != NULL && leftSubtree.maxVal > root->val) ||
            (root->right != NULL && rightSubtree.minVal < root->val)) {
        return { false, false, 0, 0, 0, 0 };
    }

    /*
        Check if the current 
        subtree is balanced
    */
    bool validBalancedTree = (abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1);

    // Compute the information for the current subtree
    SubtreeData currentSubtree;
    currentSubtree.validBST = true;
    currentSubtree.validBalancedTree = validBalancedTree;
    currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize;
    currentSubtree.treeHeight = max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1;
    
    // Finding currentSubtree.minVal
    if (root->left != NULL) {
        currentSubtree.minVal = leftSubtree.minVal;
    } 
    else {
        currentSubtree.minVal = root->val;
    }
    
    // Finding currentSubtree.mixVal
    if (root->right != NULL) {
        currentSubtree.maxVal = rightSubtree.maxVal;
    } 
    else {
        currentSubtree.maxVal = root->val;
    }

    /*
        If the current subtree is 
        a balanced BST of treeSize k, 
        we're done!
    */
    if (validBalancedTree && currentSubtree.treeSize == k) {
        found = true;
    }

    /*
        Return the information 
        for the current subtree
    */
    
    return currentSubtree;
}

/*
    Finds a balanced BST of 
    Size k rooted at 'root'
*/
int check(TreeNode* root, int k) {
    bool found = false;
    SubtreeData result = helperFunctionBalancedBST(root, k, found);
    if (found) {
        return 1;
    } 
    else {
        return 0;
    }
}
int main() {
    TreeNode * root = makeTree(4);
    root -> left = makeTree(2);
    root -> right = makeTree(5);
    root -> left -> left = makeTree(1);
    root -> left -> right = makeTree(3);
    root -> right -> right = makeTree(6);
    int k = 3;
    
    int balancedBST = check(root, k);
    if(balancedBST) {
        cout<<"Balanced BST of size k exists"<<endl;
    }
    else {
        cout<<"Balanced BST of size k doesn't exist"<<endl;
    }
    return 0;
}

Output

output

Implementation in Python

# Class to store information about a subtree
class SubtreeData:
    def __init__(self, validBST, validBalancedTree, treeSize, treeHeight, minVal, maxVal):
        self.validBST = validBST
        self.validBalancedTree = validBalancedTree
        self.treeSize = treeSize
        self.treeHeight = treeHeight
        self.minVal = minVal
        self.maxVal = maxVal
 
# A binary tree node
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

# Function to create a tree node
def makeTree(value):
    temp = TreeNode()
    temp.left = temp.right = None
    temp.val = value
    return temp
 
"""
    Helper function to find
    a balanced BST of treeSize k. It 
    returns information about the 
    subtree rooted at 'root'
"""
def helperFunctionBalancedBST(root, k, found):
    # Base case: empty subtree
    if root is None:
        return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
 
    # Recursively check the left and right subtrees
    leftSubtree = helperFunctionBalancedBST(root.left, k, found)
    if found[0]:
        return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
 
    rightSubtree = helperFunctionBalancedBST(root.right, k, found)
    if found[0]:
        return SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
 
    # Check if the current subtree is a valid BST
    if not leftSubtree.validBST or not rightSubtree.validBST or \
        (root.left and leftSubtree.maxVal > root.val) or \
        (root.right and rightSubtree.minVal < root.val):
        return SubtreeData(False, False, 0, 0, 0, 0)
 
    # Check if the current subtree is balanced
    validBalancedTree = (abs(leftSubtree.treeHeight - rightSubtree.treeHeight) <= 1)
 
    # Compute the information for the current subtree
    currentSubtree = SubtreeData(True, True, 0, 0, float('inf'), float('-inf'))
    currentSubtree.validBST = True
    currentSubtree.validBalancedTree = validBalancedTree
    currentSubtree.treeSize = 1 + leftSubtree.treeSize + rightSubtree.treeSize
    currentSubtree.treeHeight = max(leftSubtree.treeHeight, rightSubtree.treeHeight) + 1
 
    # Finding currentSubtree.minVal
    if root.left is not None:
        currentSubtree.minVal = leftSubtree.minVal
    else:
        currentSubtree.minVal = root.val
    
    # Finding currentSubtree.mixVal
    if root.right is not None:
        currentSubtree.maxVal = rightSubtree.maxVal
    else:
        currentSubtree.maxVal = root.val
 
    # If the current subtree is a balanced BST of treeSize k, we're done!
    if validBalancedTree and currentSubtree.treeSize == k:
        found[0] = True
 
    # Return the information for the current subtree
    return currentSubtree
 
"""
    Finds a balanced BST of Size k rooted at 'root'
"""
 
def check(root, k):
    found = [False]
    result = helperFunctionBalancedBST(root, k, found)
    if found[0]:
        return 1
    else:
        return 0
 
if __name__ == '__main__':
    root = makeTree(4)
    root.left = makeTree(2)
    root.right = makeTree(5)
    root.left.left = makeTree(1)
    root.left.right = makeTree(3)
    root.right.right = makeTree(6)
    k = 3
 
    balanced_bst = check(root, k)
    if balanced_bst == 1:
        print("Balanced BST of size k exists")
    else:
        print("Balanced BST of size k doesn't exist")

Output

output

Complexity Analysis

Following is the time and space complexity analysis of this code.

Time Complexity 

O(n) is the time complexity, where n indicates the number of tree nodes.

Reason: Here, we’re traversing the tree once in post-order traversal, which requires O(n) time. All other operations require O(1) time. Thus, the overall complexity is O(n).

Space Complexity

O(n) is the space complexity, where n is the tree's height.

Reason: The maximum number of function calls that can be made in the stack would equal the tree's height. In the worst case, where the tree is skewed, the height would equal n, so the space complexity would be O(n).

Frequently Asked Questions

What is a binary tree?

A binary tree is a hierarchical data structure in which each node can have not more than two children. These children are referred to as the left child and the right child.

What is a binary tree used for?

The main use of binary trees is in searching and sorting. This is because they provide a means to store data hierarchically.

What are binary search trees?

Binary search trees are trees in which, for each node, the node's value is larger than the maximum value in its left node and lesser than the minimum value in its right subtree.

What is tree traversal?

Tree traversal refers to visiting all the nodes in a tree data structure in a specific order.

What is post-order traversal?

Post-order traversal is a traversal in which we travel first to the left subtree of the node, then to the right subtree, and then to the node itself.

Conclusion

In this article, we learned about the solution to a famous problem of “checking if the binary tree has a balanced BST of size K.” We also learned about its implementation in popular programming languages and their complexity analysis. 

You can refer to the following articles to learn more about tree data structure. 

For placement preparations, you must look at the problemsinterview experiences, and interview bundles. Enrol in our courses and refer to the mock tests and problems available; look at the Problem Sheets, interview experiences, and interview bundle for placement preparations. You can also book an interview session with us.

Consider our paid courses, however, to give your career a competitive advantage!
 

Happy Coding!

Live masterclass