Question 76 : Check if a binary tree is binary search tree or not in java

In this post, we will see how to check if a given binary tree is a binary search tree or not. This is one of important interview questions on the binary tree.

We will see two approaches to check if binary tree is bst or not.

Question 75 : Convert sorted Linked List to balanced BST

In this post, we will see how to convert sorted LinkedList to a balanced binary search tree.

There are two ways to do it.

Question 74 : Convert sorted array to balanced BST

Algorithm:

You might know that inorder traversal of binary search tree results in sorted array. We will use this property to convert sorted array to balanced binary search tree, so middle element of array ora sub array will always be root for that array or subarray.

• Initialise two variables start and end with 0 and arr.length -1.
• Find middle element of array using start and end.
• Make middle element root element of tree.
• Recursively traverse left subtree, find middle and make it root node of left subtree
• Recursively traverse right subtree, find middle and make it root node of right subtree.

Question 73 : Find inorder successor in a Binary search Tree

 Problem

Given a Binary search Tree and a target node value. Find the inorder successor of the given node value in the Binary Search tree given. Inorder successor of any node ‘x’ is basically the node which gets traversed immediately after ‘x’ in the Inorder traversal of a tree.

Question 72 : How to find lowest common ancestor(LCA) in binary search tree.

 You need to write a program to find LCA in the binary search tree.

Question 71 : How can you find minimum and maximum elements in binary search tree?

 Solution : Leftmost and rightmost nodes of binary search tree are minimum and maximum nodes respectively

Question 70 : Can you write algorithm to delete a node in binary search tree

 There are three cases which we may need to consider while deleting a node from binary search tree.

• If node has no child
• If node has one child
• If node has two children.

Question 69 : Can you write algorithm to insert a node in binary search tree

 

Binary search tree is a special type of Binary tree which have following properties.

• Nodes which are smaller than root will be in left subtree.
• Nodes which are greater than root will be right subtree.
• It should not have duplicate nodes
• Both left and right subtree also should be binary search tree.

Question 68 : What is binary search tree?

 A binary search tree is a special type of binary tree which have the following properties.

• Nodes that are smaller than the root will be in the left subtree.
• Nodes that are greater than the root will be the right subtree.
• It should not have duplicate nodes
• Both left and right subtree also should be binary search trees.