Tag Archives: Binary Search Tree

Range Sum of BST

By | | , , ,
Leave a comment

Let’s discuss a problem range sum of BST (binary search tree).

In this problem, 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].

Binary Search Tree (BST)

In binary search tree, the value of all the nodes in the left sub-tree is less than the value of the root node. Similarly, Value of all the nodes in the right sub-tree is greater than or equal to the value of the root.

For example

In the below example (image), we have to find the sum of all nodes whose value lies in the range of 7 to 15 (inclusive).

The nodes 7, 10, and 15 lie in this range and its sum is 32.

→

Validate Binary Search Tree | Binary Tree is BST or Not

By | | , , ,
Leave a comment

In this post, I am going to discuss a very famous interview problem validate binary search tree or in other words check if a binary tree is BST or not.

Given the root of a binary tree, We have to write a code to check if it is a binary search tree (BST) or not.

The property of a valid binary search tree (BST) is:

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

For example –

→

Recover Binary Search Tree

By | | , , ,
Leave a comment

In this problem, we have given the root of a binary search tree (BST), where exactly two nodes of the tree were swapped by mistake. Write a code to recover binary search tree without changing its structure.

The solution using O(n) space is pretty straight forward. Can you solve this problem using constant space?

→