Validate Binary Search Tree | Binary Tree is BST or Not

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 –

Binary Tree Level Order Traversal II

Binary Tree Level Order Traversal II. Given a binary tree, return the bottom-up level order traversal of its node’s values.  (ie, from left to right, level by level from leaf to root).

OR

Given a binary tree, return the reverse level order traversal of its nodes’ values. (i.e, from left to right and from the last level to starting level).