# Problem Statement
Given a Binary Tree, figure out whether it’s a Binary Search Tree. In a binary search tree, each node’s key value is smaller than the key value of all nodes in the right subtree, and are greater than the key values of all nodes in the left subtree i.e. L < N < RL<N<R.

Below is an example of binary tree that is a valid BST.

Below is an example of a binary tree that is not a BST

<br>

# Hint
* Recursion
* Inorder traversal

<br>

# Try it yourself

bool is_bst(BinaryTreeNode* root) {
   //TODO: Write - Your - Code
    return false;
}

#include <iostream>
#include <vector>
#include <string>
#include <list>
#include <queue>
#include <algorithm>
#include <assert.h>
#include <time.h>
#include <math.h>
#include <stack>
#include <cstdlib>
using namespace std;


struct BinaryTreeNode
{
    int data;
    BinaryTreeNode* left;
    BinaryTreeNode* right;
    BinaryTreeNode* parent;

    // below data members used only for some of the problems
    BinaryTreeNode* next;
    int count;

    BinaryTreeNode(int d) : data(d), left(nullptr), right(nullptr), next(nullptr), parent(nullptr), count(0) {
    }
};

BinaryTreeNode* insert_bst(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (d < parent->data) {
    parent->left = pNew;
  } else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* find_in_bst(BinaryTreeNode* root, int d) {
  if(root == nullptr)
    return nullptr;

  if(root->data == d) {
    return root;
  }
  else if( root->data > d)
  {
    return find_in_bst(root->left, d);
  }
  else
  {
    return find_in_bst(root->right,d);
  }
}

BinaryTreeNode* insert_binary_tree(BinaryTreeNode* root, int d) {
  BinaryTreeNode* pNew = new BinaryTreeNode(d);
  if (root == nullptr) {
    return pNew;
  }

  BinaryTreeNode* parent = nullptr;
  BinaryTreeNode* pTemp = root;
  while (pTemp != nullptr) {
    parent = pTemp;
    if (d < pTemp->data) {
      pTemp = pTemp->left;
    } else {
      pTemp = pTemp->right;
    }
  }

  if (rand()%2 == 0) {
    parent->left = pNew;
  }
  else {
    parent->right = pNew;
  }

  return root;
}

BinaryTreeNode* create_BinaryTree(int count) {
  BinaryTreeNode* root = nullptr;
  for (int i = 0; i < count; ++i) {
    int r = rand() % 100;
    root = insert_binary_tree(root, r);
  }
  return root;
}

void display_inorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  display_inorder(node->left);
  cout << node->data << ", ";
  display_inorder(node->right);
}

void get_inorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  get_inorder(node->left, output);
  output.push_back(node->data);
  get_inorder(node->right, output);
}

void display_preorder(BinaryTreeNode* node) {
  if (node == nullptr) {
    return;
  }
  cout << node->data << ", ";

  display_preorder(node->left);
  display_preorder(node->right);
}

void get_preorder(BinaryTreeNode* node, vector<int>& output) {
  if (node == nullptr) {
    return;
  }
  output.push_back(node->data);
  get_inorder(node->left, output);
  get_inorder(node->right, output);
}

BinaryTreeNode* create_BST(vector<int>& v) {
  BinaryTreeNode* root = nullptr;
  int count = 0;
  for (int x : v) {
    root = insert_bst(root, x);
    if (count % 50000 == 0) {
      cout << "Inserted " << count << endl;
    }
    ++count;
  }
  return root;
}

BinaryTreeNode* create_random_BST(int count) {
  BinaryTreeNode* root = nullptr;
  srand(time(NULL));
  for (int i = 0; i < count; ++i) {
      int r =  rand() % 997;
      root = insert_bst(root, r);
  }
  return root;
}

void binary_tree_to_vector_rec(BinaryTreeNode* root, vector<int>& v) {
  if (root == nullptr) {
    return;
  }

  binary_tree_to_vector_rec(root->left, v);
  v.push_back(root->data);
  binary_tree_to_vector_rec(root->right, v);
}

vector<int> binary_tree_to_vector(BinaryTreeNode* root) {
  vector<int> v;
  binary_tree_to_vector_rec(root, v);
  return v;
}

void display_level_order(BinaryTreeNode* root) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    cout << temp->data << ", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      cout << endl;
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  cout << endl;
}
string display_BT(BinaryTreeNode* root) {
  string result = "";
  if (root == nullptr) {
    return "";
  }

  queue<BinaryTreeNode*> q;
  q.push(root);
  q.push(nullptr);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();
    result += std::to_string(temp->data) +", ";
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }

    if (q.front() == nullptr) {
      q.pop();
      if (!q.empty()) {
        q.push(nullptr);
      }
    }

  }
  return result;
}

void get_level_order(BinaryTreeNode* root, vector<int>& output) {
  if (root == nullptr) {
    return;
  }

  queue<BinaryTreeNode*> q;
  q.push(root);

  while (!q.empty()) {
    BinaryTreeNode* temp = q.front();
    q.pop();

    output.push_back(temp->data);
    
    if (temp->left != nullptr) {
      q.push(temp->left);
    }

    if (temp->right != nullptr) {
      q.push(temp->right);
    }
  }
}

void another_display_tree(BinaryTreeNode* root, int tabs) {
  if (root != nullptr) {
    int i;

    if (root->left != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "L" << root->left->data << endl;
    }

    if (root->right != nullptr) {
      for(i = 0; i < tabs+4; ++i) {
        cout << ' ';
      }
      cout << "R" << root->right->data << endl;
    }

    another_display_tree(root->left, tabs + 4);
    another_display_tree(root->right, tabs + 4);
  }
}

void another_display_tree(BinaryTreeNode* root) {
  if (root != nullptr) {
    cout << root->data << endl;
    another_display_tree(root, 0);
  }
}

bool is_identical_tree(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  else if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            is_identical_tree(root1->left, root2->left) &&
            is_identical_tree(root1->right, root2->right));
  }
  else {
    return false;
  }
}

void populate_parents_rec(BinaryTreeNode* root, BinaryTreeNode* parent) {
  if (root == nullptr) {
    return;
  }

  root->parent = parent;

  populate_parents_rec(root->left, root);
  populate_parents_rec(root->right, root);
}

void populate_parents(BinaryTreeNode* root) {
  populate_parents_rec(root, nullptr);
}

bool are_identical_trees(BinaryTreeNode* root1, BinaryTreeNode* root2) {
  if (root1 == nullptr && root2 == nullptr) {
    return true;
  }
  
  if (root1 != nullptr && root2 != nullptr) {
    return ((root1->data == root2->data) &&
            are_identical_trees(root1->left, root2->left) &&
            are_identical_trees(root1->right, root2->right));
  }

  return false;
}

void print(vector<int>& v) {
  cout << "vector = {";
  for (int x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
void print_list(vector<T>& v) {
  cout << "{ ";
  for (auto x : v) {
    cout << x << ",";
  }
  cout << "}" << endl;
}

template <class T>
bool is_equal(vector<T>& v1, vector<T>& v2) {
  if (v1.size() != v2.size()) {
    return false;
  }

  int idx = 0;
  for (auto x : v1) {
    if (x != v2[idx]) {
      return false;
    }
    ++idx;
  }

  return true;
}

template<typename T>
vector<T> create_random_vector(int length, T max_value = 100) {
  vector<T> v(length);
  srand (time(nullptr));
  for(T i = 0; i < length; ++i) {
    v[i] = static_cast<T>(rand() % max_value);
  }
  return v;
}

vector<int> create_random_vector(int length, int max_value = 100) {
  vector<int> v(length);
  srand (time(nullptr));
  for(int i = 0; i < length; ++i) {
    v[i] = rand() % max_value;
  }
  return v;
}

int find_in_vector(vector<int>& v, int k) {
  for (int i = 0; i < v.size(); ++i) {
    if (k == v[i]) {
      return i;
    }
  }
  return -1;
}

bool is_sorted(vector<int> v) {

  for (int i = 1; i < v.size(); ++i) {
    if (v[i] < v[i-1]) {
      return false;
    }
  }

  return true;
}

class isBST{
  public static boolean is_bst(
      BinaryTreeNode root) {
    //TODO: Write - Your - Code
    return false;
  }
}

import java.util.*;
import java.math.*;

class BinaryTreeNode
{
    public int data;
    public BinaryTreeNode left;
    public BinaryTreeNode right;

    // below data members used only for some of the problems
    public BinaryTreeNode next;
    public BinaryTreeNode parent;
    public int count;

    public BinaryTreeNode(int d) {
      data = d;
      left = null;
      right = null;
      parent = null;
      count = 0;
    }
}
class BinaryTree {

public static BinaryTreeNode root;

public BinaryTree() {
  root = null;
}

public BinaryTree(BinaryTreeNode head) {
  this.root = head;
}

public static BinaryTreeNode insert(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  if (d <= parent.data) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode insert_BT(BinaryTreeNode root, int d) {

  BinaryTreeNode pNew = new BinaryTreeNode(d);
  if (root == null) {
    return pNew;
  }

  BinaryTreeNode parent = null;
  BinaryTreeNode pTemp = root;
  while (pTemp != null) {
    parent = pTemp;
    if (d <= pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }

  Random generator = new Random();
  int dir = generator.nextInt(1000);

  if (dir%2 == 0) {
    parent.left = pNew;
    pNew.parent = parent;
  } else {
    parent.right = pNew;
    pNew.parent = parent;
  }  
  return root;
}

public static BinaryTreeNode find_in_bst(BinaryTreeNode root, int d){
  if(root == null)
    return null;

  if(root.data == d) {
    return root;
  }
  else if(root.data > d){
    return find_in_bst(root.left,d);
  }
  else{
    return find_in_bst(root.right,d);
  }
}


public static void display_inorder(BinaryTreeNode node) {
  if (node == null) {
    return;
  }
  display_inorder(node.left);
  if(node.parent != null)
  {
    //System.out.print(String.format("[%d - %d]",node.parent.data, node.count));
  }
  System.out.print(node.data + ", ");
  display_inorder(node.right);
}

public static void get_inorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  get_inorder(node.left, output);
  output.add(node.data);
  get_inorder(node.right, output);
}

public static void get_preorder(BinaryTreeNode node, List<Integer> output) {
  if (node == null) {
    return;
  }
  output.add(node.data);
  get_preorder(node.left, output);
  get_preorder(node.right, output);
}

public static BinaryTreeNode create_BST(List<Integer> l) {
  BinaryTreeNode root = null;
  for (Integer x : l) {
    root = insert(root, x);
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count, int max_value) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert(root, generator.nextInt(max_value));
  }
  return root;
}

public static BinaryTreeNode create_random_BST(int count) {
  return create_random_BST(count, Integer.MAX_VALUE);
}

public static BinaryTreeNode create_binary_tree(int count) {
  BinaryTreeNode root = null;
  for (int i = 0; i < count; ++i) {
    Random generator = new Random();
    root = insert_BT(root, generator.nextInt(100));
  }
  return root;
}

private static void populate_parents_rec(BinaryTreeNode root, BinaryTreeNode parent) {
  if (root == null) {
    return;
  }

  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

public static void populate_parents(BinaryTreeNode root) {
  populate_parents_rec(root, null);
}

public static void bst_to_arraylist_rec(BinaryTreeNode root, ArrayList<Integer> arr) {
  if (root == null) {
    return;
  }

  bst_to_arraylist_rec(root.left, arr);
  arr.add(root.data);
  bst_to_arraylist_rec(root.right, arr);
}

public static ArrayList<Integer> bst_to_arraylist(BinaryTreeNode root) {
  ArrayList<Integer> arr = new ArrayList<Integer>();
  bst_to_arraylist_rec(root, arr);
  return arr;
}

public static void another_display_tree(BinaryTreeNode root, int tabs) {
  if (root != null) {
    int i;

    if (root.left != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("L" + root.left.data + "\n");
    }

    if (root.right != null) {
      for(i = 0; i < tabs+4; ++i) {
        System.out.print(" ");
      }
      System.out.print("R" + root.right.data + "\n");
    }

    another_display_tree(root.left, tabs + 4);
    another_display_tree(root.right, tabs + 4);
  }
}

public static void another_display_tree(BinaryTreeNode root) {
  if (root != null) {
    System.out.print(root.data + "\n");
    another_display_tree(root, 0);
  }
}

public static void display_level_order(BinaryTreeNode root) {
  if(root == null)
    return;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    System.out.print(temp.data + ", ");

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
    System.out.println();
}

public static List<Integer> get_level_order(BinaryTreeNode root) {

  List<Integer> output = new ArrayList<Integer>();

  if(root == null)
    return output;

  ArrayDeque<BinaryTreeNode> queue = new ArrayDeque<BinaryTreeNode>();
  queue.addLast(root);

  while(!queue.isEmpty()){
    BinaryTreeNode temp = queue.removeFirst();
    // System.out.print(temp.data + ", ");
    output.add(temp.data);

    if(temp.left != null) {
      queue.addLast(temp.left);
      //System.out.println(temp.left.data + "LEFT");
    }

    if(temp.right != null){
      queue.addLast(temp.right);
      //System.out.println(temp.right.data + "RIGHT");
    }
  }
  return output;
}

public static boolean is_identical_tree(BinaryTreeNode root1, BinaryTreeNode root2) {
  if (root1 == null && root2 == null) {
    return true;
  }
  else if (root1 != null && root2 != null) {
    return ((root1.data == root2.data) &&
            is_identical_tree(root1.left, root2.left) &&
            is_identical_tree(root1.right, root2.right));
  }
  else {
    return false;
  }
}
}

Java

def is_bst(root):
  #TODO: Write - Your - Code
  return False

import os, sys
utils_path = os.path.join('..', '..', '..', '..', 'problems', 'utils', 'python')
sys.path.append(utils_path)
from collections import deque

class BinaryTreeNode:
  def __init__(self, data):
    self.data = data
    self.left = None
    self.right = None
    self.next = None
    self.parent = None


import random

def insert_binary_tree(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d <= parent.data:
    parent.right = pNew
  else:
    parent.left = pNew

  return root

def insert(root, d):
  pNew = BinaryTreeNode(d)
  if root == None:
    return pNew

  parent = None
  pTemp = root
  while (pTemp != None): 
    parent = pTemp
    if d < pTemp.data:
      pTemp = pTemp.left
    else:
      pTemp = pTemp.right

  if d < parent.data:
    parent.left = pNew
  else:
    parent.right = pNew

  return root

def find_in_bst(root, d):
  if root == None:
    return None

  if root.data == d:
    return root
  elif root.data > d:
    return find_in_bst(root.left, d)
  else:
    return find_in_bst(root.right, d)

# find node in inorder 
# works for both BST and binary tree
def find_node(root, d):
  if root == None:
    return

  if root.data == d:
    return root

  temp = find_node(root.left, d)
  if temp != None:
    return temp

  return find_node(root.right, d) 

def display_inorder(node):
  if node == None:
    return

  display_inorder(node.left)
  print(str(node.data), end = ", ")
  display_inorder(node.right)

def create_BST(arr):
  root = None
  for x in arr:
    root = insert(root, x)
  return root

def create_binary_tree(count):
  root = None
  for i in range(1, count):
    root = insert_binary_tree(root, random.randrange(1,100))
  return root

def create_random_BST(count):
  root = None;
  for i in range(1, count):
    root = insert(root, random.randrange(200, 300))
  return root

def bst_to_list_rec(root, lst):
  if root == None:
    return

  bst_to_list_rec(root.left, lst)
  lst.append(root.data)
  bst_to_list_rec(root.right, lst)

def bst_to_list(root):
  lst = []
  bst_to_list_rec(root, lst)
  return lst

def insert_at_head(head, data):
  newNode = LinkedListNode(data)
  newNode.next = head
  return newNode

def populate_parents_rec(root, parent):
  if root == None:
    return 
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)

def populate_parents(root):
  populate_parents_rec(root, None)

def display_level_order(root):
  if root == None:
    return
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    print(str(temp.data), end = ",")
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  print

def get_level_order(root):
  output = []
  if root == None:
    return output
  
  q = deque()
  q.append(root)

  while q:
    temp = q.popleft()
    output.append(temp.data)
    if temp.left != None:
      q.append(temp.left)
    if temp.right != None:
      q.append(temp.right)

  return output

def get_inorder_helper(root, output):
  if root == None:
    return output

  output = get_inorder_helper(root.left, output)
  output.append(root.data)
  output = get_inorder_helper(root.right, output)
  
  return output

def get_inorder(root):
  output = []
  return get_inorder_helper(root, output)

def is_identical_tree(root1,root2):
  if root1 == None and root2 == None:
    return True

  if root1 != None and root2 != None and root1.data == root2.data: 
    return is_identical_tree(root1.left,root2.left) and is_identical_tree(root1.right,root2.right)

  return False

Python

let is_bst = function(root) {
  //TODO: Write - Your - Code
  return false;
};

class TreeNode {
  constructor(data) {
    this.data = data;
    this.children = [];
  }

  display_level_order() {
    if (!this) {
      return;
    }
    let q = [];
    q.push(this);

    while (q.length > 0) {
      let temp = q.shift();
      console.log(temp.data + " ");

      for (let c in temp.children) {
        q.push(temp.children[c]);
      }
    }
  }
}

class BinaryTreeNode {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
    this.next = null;
    this.parent = null;
  }
}

class LinkedListNode {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
    this.arbitrary = null;
  }
}

let insert_binary_tree = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root
  while (pTemp) {
    let parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d <= parent.data) {
    parent.right = pNew;
  } else {
    parent.left = pNew;
  }

  return root;
}

let insert = function(root, d) {
  let pNew = new BinaryTreeNode(d);
  if (!root) {
    return pNew;
  }

  let parent = null;
  let pTemp = root;
  while (pTemp) {
    parent = pTemp;
    if (d < pTemp.data) {
      pTemp = pTemp.left;
    } else {
      pTemp = pTemp.right;
    }
  }
  if (d < parent.data) {
    parent.left = pNew;
  } else {
    parent.right = pNew;
  }

  return root;
}

let find_in_bst = function(root, d) {
  if (!root) {
    return null;
  }

  if (root.data === d) {
    return root;
  } else if (root.data > d) {
    return find_in_bst(root.left, d);
  } else {
    return find_in_bst(root.right, d);
  }
}
// find node in inorder 
// works for both BST and binary tree
let find_node = function(root, d) {
  if (!root) {
    return;
  }

  if (root.data === d) {
    return root;
  }

  let temp = find_node(root.left, d);
  if (temp) {
    return temp;
  }

  return find_node(root.right, d);
}

let display_inorder = function(node) {
  if (!node) {
    return;
  }

  display_inorder(node.left);
  console.log(node.data);
  display_inorder(node.right);
}

let create_BST = function(arr) {
  let root = null;
  for (let x in arr) {
    root = insert(root, arr[x]);
  }
  return root;
}

let create_binary_tree = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert_binary_tree(root, Math.floor(Math.random() * 100 + 1));
  }
  return root;
}

let create_random_BST = function(count) {
  let root = null;
  for (let i = 1; i < count; i++) {
    root = insert(root, Math.floor(Math.random() * 100 + 200));
  }
  return root;
}

let bst_to_list_rec = function(root, lst) {
  if (!root) {
    return;
  }

  bst_to_list_rec(root.left, lst);
  lst.push(root.data);
  bst_to_list_rec(root.right, lst);
}

let bst_to_list = function(root) {
  let lst = [];
  bst_to_list_rec(root, lst);
  return lst;
}

let populate_parents_rec = function(root, parent) {
  if (!root) {
    return;
  }
  root.parent = parent;

  populate_parents_rec(root.left, root);
  populate_parents_rec(root.right, root);
}

let populate_parents = function(root) {
  populate_parents_rec(root, null);
}

let display_level_order = function(root) {
  if (!root) {
    return;
  }
  let q = [];
  q.push(root);
  let print_level = '';
  while (q.length > 0) {
    let temp = q.shift();
    print_level += temp.data + ",";
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right)
    }
  }
  console.log(print_level);
}

let get_level_order = function(root) {
  let output = [];
  if (!root) {
    return output;
  }

  let q = [];
  q.push(root);

  while (q.length > 0) {
    let temp = q.shift();
    output.push(temp.data);
    if (temp.left) {
      q.push(temp.left);
    }
    if (temp.right) {
      q.push(temp.right);
    }
  }
  return output;
}

let get_inorder_helper = function(root, output) {
  if (!root) {
    return output;
  }

  output = get_inorder_helper(root.left, output);
  output.push(root.data);
  output = get_inorder_helper(root.right, output);

  return output;
}

let get_inorder = function(root) {
  let output = [];
  return get_inorder_helper(root, output);
}

let is_identical_tree = function(root1, root2) {
  if (!root1 && !root2) {
    return true;
  }

  if (root1 && root2 && root1.data === root2.data) {
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right);
  }

  return false;
}

JavaScript

def is_bst(root)
  #TODO: Write - Your - Code
  return false
end

class TreeNode
  attr_accessor :data, :children
  def initialize(data)
    @data = data
    @children = []
  end

  def display_level_order()
    if (!self)
      return
    end
    q = []
    q.push(self)

    while (q.length > 0)
      temp = q.shift()
      print(temp.data.to_s + ",")

      temp.children.each do |c|
        q.push(c)
      end
    end
  end

end

class BinaryTreeNode
  attr_accessor :data, :left, :right, :next, :parent, :count
  def initialize(data)
    @data = data
    @left = nil
    @right = nil
    @next = nil
    @parent = nil
    @count = -1
  end
end

def insert_binary_tree(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d <= parent.data)
    parent.right = pNew
  else
    parent.left = pNew
  end

  return root
end

def insert(root, d)
  pNew = BinaryTreeNode.new(d)
  if (!root)
    return pNew
  end

  parent = nil
  pTemp = root
  while (pTemp)
    parent = pTemp
    if (d < pTemp.data)
      pTemp = pTemp.left
    else
      pTemp = pTemp.right
    end
  end
  if (d < parent.data)
    parent.left = pNew
  else
    parent.right = pNew
  end

  return root
end

def find_in_bst(root, d)
  if (!root)
    return nil
  end

  if (root.data == d)
    return root
  elsif (root.data > d)
    return find_in_bst(root.left, d)
  else
    return find_in_bst(root.right, d)
  end
end

# find node in inorder
# works for both BST and binary tree
def find_node(root, d)
  if (!root)
    return
  end

  if (root.data == d)
    return root
  end

  temp = find_node(root.left, d)
  if (temp)
    return temp
  end

  return find_node(root.right, d)
end

def display_inorder(node)
  if (!node)
    return
  end

  display_inorder(node.left)
  print (node.data.to_s + ", ")
  display_inorder(node.right)
end
def create_BST(arr)
  root = nil
  arr.each do |x|
    root = insert(root, x)
  end
  return root
end

def create_binary_tree(count)
  root = nil
  (count-1).times do |i|
    root = insert_binary_tree(root, (rand * 100 + 1).floor)
  end
  return root
end

def create_random_BST(count)
  root = nil
  (count-1).times do |i|
    root = insert(root, (rand * 100 + 200).floor)
  end
  return root
end

def bst_to_list_rec(root, lst)
  if (!root)
    return
  end

  bst_to_list_rec(root.left, lst)
  lst.push(root.data)
  bst_to_list_rec(root.right, lst)
end

def bst_to_list(root)
  lst = []
  bst_to_list_rec(root, lst)
  return lst
end

def populate_parents_rec(root, parent)
  if (!root)
    return
  end
  root.parent = parent

  populate_parents_rec(root.left, root)
  populate_parents_rec(root.right, root)
end

def populate_parents(root)
  populate_parents_rec(root, nil)
end

def display_level_order(root)
  if (!root)
    return
  end
  q = []
  q.push(root)
  print_level = ''
  while (q.length > 0)
    temp = q.shift()
    print_level += temp.data.to_s + ","
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  print (print_level)
end

def get_level_order(root)
  output = []
  if (!root)
    return output
  end

  q = []
  q.push(root)

  while (q.length > 0)
    temp = q.shift()
    output.push(temp.data)
    if (temp.left)
      q.push(temp.left)
    end
    if (temp.right)
      q.push(temp.right)
    end
  end
  return output
end

def get_inorder_helper(root, output)
  if (!root)
    return output
  end

  output = get_inorder_helper(root.left, output)
  output.push(root.data)
  output = get_inorder_helper(root.right, output)

  return output
end

def get_inorder(root)
  output = []
  return get_inorder_helper(root, output)
end

def is_identical_tree(root1, root2)
  if (!root1 && !root2)
    return true
  end

  if (root1 && root2 && root1.data == root2.data)
    return is_identical_tree(root1.left, root2.left) && is_identical_tree(root1.right, root2.right)
  end

  return false
end

Ruby

bool is_bst_rec(
    BinaryTreeNode* root,
    int min_value,
    int max_value) {

  if (root == nullptr) {
    return true;
  }

  if (root->data < min_value || 
      root->data > max_value) {
    return false;
  }

  return 
    is_bst_rec(root->left, min_value, root->data) &&
      is_bst_rec(root->right, root->data, max_value);
}

bool is_bst(BinaryTreeNode* root) {
  return 
    is_bst_rec(
      root,
      numeric_limits<int>::min(), 
      numeric_limits<int>::max());
}

void test_is_bst() {
  BinaryTreeNode* root = create_random_BST(15);
  BinaryTreeNode* root2 = create_BinaryTree(20);
  root2->left = root;
  root2->right = root;
  display_level_order(root);
  display_level_order(root2);
  assert(is_bst(root));
  assert(!is_bst(root2));
}

int main(int argc, char* argv[]) {

  test_is_bst();
}

class isBST{
  private static boolean is_bst_rec(
      BinaryTreeNode root,
      int min_value,
      int max_value) {

    if (root == null) {
      return true;
    }

    if (root.data < min_value || 
        root.data > max_value) {
      return false;
    }

    return 
      is_bst_rec(root.left, min_value, root.data) &&
        is_bst_rec(root.right, root.data, max_value);
  }

  public static boolean is_bst(
      BinaryTreeNode root) {
  
    return 
      is_bst_rec(
        root, Integer.MIN_VALUE, Integer.MAX_VALUE);
  }
 
  public static void main(String[] argv) {
  
    BinaryTreeNode root = BinaryTree.create_random_BST(5,100);
    BinaryTree.display_level_order(root);
    System.out.println();
    System.out.println("Is it BST?: " + Boolean.toString(is_bst(root)));

    BinaryTreeNode root2 = BinaryTree.create_binary_tree(5);
    System.out.println();
    BinaryTree.display_level_order(root2);    
    System.out.println("Is it BST?: " + Boolean.toString(is_bst(root2)));
  }
}

def is_bst_rec(root, min_value, max_value):
  if root == None:
    return True

  if root.data < min_value or root.data > max_value:
    return False

  return is_bst_rec(root.left, min_value, root.data) and is_bst_rec(root.right, root.data, max_value)

def is_bst(root):
  return is_bst_rec(root, -sys.maxint - 1, sys.maxint)


root = create_random_BST(15)
root2 = create_random_BST(15)
root2.data = 100
print("\nInOrder Traversal")
display_inorder(root)
print("\nIs BST\n\n")
print("\nInOrder Traversal")
display_inorder(root2)
print("\nIs not BST\n\n")

def is_bst_rec(root, min_value, max_value)
  if (!root)
    return true
  end

  if (root.data < min_value || root.data > max_value)
    return false
  end

  return is_bst_rec(root.left, min_value, root.data) && is_bst_rec(root.right, root.data, max_value)
end

def is_bst(root)
  machine_max_signed = 2**((root.data.size * 8)-1) - 1
  return is_bst_rec(root, -machine_max_signed - 1, machine_max_signed)
end

def main()
  root = create_random_BST(15)
  root2 = create_random_BST(15)
  root2.data = 100
  print "\nInOrder Traversal\n"
  display_inorder(root)
  print "\nIs BST?: " + is_bst(root).to_s
  print "\nInOrder Traversal\n"
  display_inorder(root2)
  print "\nIs BST?: " + is_bst(root2).to_s
end

main()

# Solution Explanation
## Runtime Complexity
The runtime complexity of this solution is linear, O(n).

## Memory Complexity 
The memory complexity of this solution is linear, O(n).

<br>

## Solution Breakdown
There are several ways of solving this problem. A basic algorithm would be to check on each node where the maximum value of its left sub-tree is less than the node’s data and the minimum value of its right sub-tree is greater than the node’s data. This is highly inefficient as for each node, both of its left and right sub-trees are explored.

Another approach would be to do a regular in-order traversal and in each recursive call, pass maximum and minimum bounds to check whether the current node’s value is within the given bounds. This approach is efficient compared to the one above.

> Practice problems like this and many more by checking out our [Grokking the Coding Interview: Patterns for Coding Questions](https://www.educative.io/courses/grokking-the-coding-interview) course!

Given a binary tree, figure out whether it's a BST.

Is Binary Tree a Binary Search Tree?

Problem Statement

Hint

Try it yourself

Solution

Solution Explanation

Runtime Complexity

Memory Complexity

Solution Breakdown