Given a Binary Tree, the task is to check if the given binary tree is a Binary Search Tree or not. If found to be true, then print “YES”. Otherwise, print “NO”.
Examples:
Input:
9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8Output: YES
Explanation: Since the left subtree of each node of the tree consists of smaller valued nodes and the right subtree of each node of the tree consists of larger valued nodes. Therefore, the required is output is “YES”.Input:
5 / \ 6 3 / \ \ 4 9 2Output: NO
Recursive Approach: Refer to the previous post to solve this problem using recursion.
Time Complexity: O(N) where N is the count of nodes in the Binary Tree.
Auxiliary Space: O(N)
Iterative Approach: To solve the problem iteratively, use Stack. Follow the steps below to solve the problem:
- Initialize a Stack to store the nodes along with its left subtree.
- Initialize a variable, say prev, to store previous visited node of the Binary Tree.
- Traverse the tree and push the root node and left subtree of each node into the stack and check if the data value of the prev node is greater than or equal to the data value of the current visited node or not. If found to be true, then print “NO”.
- Otherwise, print “YES”.
Below is the implementation of the above approach.
C++
// C++ program to implement// the above approach#include <bits/stdc++.h>using namespace std;// Structure of a tree nodestruct TreeNode { // Stores data value of a node int data; // Stores left subtree // of a tree node TreeNode* left; // Stores right subtree // of a tree node TreeNode* right; // Initialization of // a tree node TreeNode(int val) { // Update data data = val; // Update left and right left = right = NULL; }};// Function to check if a binary tree// is binary search tree or notbool checkTreeIsBST(TreeNode *root) { // Stores root node and left // subtree of each node stack<TreeNode* > Stack; // Stores previous visited node TreeNode* prev = NULL; // Traverse the binary tree while (!Stack.empty() || root != NULL) { // Traverse left subtree while (root != NULL) { // Insert root into Stack Stack.push(root); // Update root root = root->left; } // Stores top element of Stack root = Stack.top(); // Remove the top element of Stack Stack.pop(); // If data value of root node less // than data value of left subtree if(prev != NULL && root->data <= prev->data) { return false; } // Update prev prev = root; // Traverse right subtree // of the tree root = root->right; } return true;}// Driver Codeint main(){ /* 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 */ // Initialize binary tree TreeNode *root = new TreeNode(9); root->left = new TreeNode(6); root->right = new TreeNode(10); root->left->left = new TreeNode(4); root->left->right = new TreeNode(7); root->right->right = new TreeNode(11); root->left->left->left = new TreeNode(3); root->left->left->right = new TreeNode(5); root->left->right->right = new TreeNode(8); if (checkTreeIsBST(root)) { cout<<"YES"; } else { cout<<"NO"; }} |
Java
// Java program to implement// the above approachimport java.util.*;class GFG{// Structure of a tree nodestatic class TreeNode { // Stores data value of a node int data; // Stores left subtree // of a tree node TreeNode left; // Stores right subtree // of a tree node TreeNode right; // Initialization of // a tree node TreeNode(int val) { // Update data data = val; // Update left and right left = right = null; }};// Function to check if a binary tree// is binary search tree or notstatic boolean checkTreeIsBST(TreeNode root) { // Stores root node and left // subtree of each node Stack<TreeNode > Stack = new Stack<TreeNode >(); // Stores previous visited node TreeNode prev = null; // Traverse the binary tree while (!Stack.isEmpty() || root != null) { // Traverse left subtree while (root != null) { // Insert root into Stack Stack.add(root); // Update root root = root.left; } // Stores top element of Stack root = Stack.peek(); // Remove the top element of Stack Stack.pop(); // If data value of root node less // than data value of left subtree if(prev != null && root.data <= prev.data) { return false; } // Update prev prev = root; // Traverse right subtree // of the tree root = root.right; } return true;}// Driver Codepublic static void main(String[] args){ /* 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 */ // Initialize binary tree TreeNode root = new TreeNode(9); root.left = new TreeNode(6); root.right = new TreeNode(10); root.left.left = new TreeNode(4); root.left.right = new TreeNode(7); root.right.right = new TreeNode(11); root.left.left.left = new TreeNode(3); root.left.left.right = new TreeNode(5); root.left.right.right = new TreeNode(8); if (checkTreeIsBST(root)) { System.out.print("YES"); } else { System.out.print("NO"); }}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to implement# the above approach# Structure of a tree nodeclass TreeNode: def __init__(self, data: int) -> None: # Stores data value of a node self.data = data # Stores left subtree # of a tree node self.left = None # Stores right subtree # of a tree node self.right = None# Function to check if a binary tree# is binary search tree or notdef checkTreeIsBST(root: TreeNode) -> bool: # Stores root node and left # subtree of each node Stack = [] # Stores previous visited node prev = None # Traverse the binary tree while (Stack or root): # Traverse left subtree while root: # Insert root into Stack Stack.append(root) # Update root root = root.left # Stores top element of Stack # Remove the top element of Stack root = Stack.pop() # If data value of root node less # than data value of left subtree if (prev and root.data <= prev.data): return False # Update prev prev = root # Traverse right subtree # of the tree root = root.right return True# Driver Codeif __name__ == "__main__": ''' 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 ''' # Initialize binary tree root = TreeNode(9) root.left = TreeNode(6) root.right = TreeNode(10) root.left.left = TreeNode(4) root.left.right = TreeNode(7) root.right.right = TreeNode(11) root.left.left.left = TreeNode(3) root.left.left.right = TreeNode(5) root.left.right.right = TreeNode(8) if checkTreeIsBST(root): print("YES") else: print("NO")# This code is contributed by sanjeev2552 |
C#
// C# program to implement// the above approachusing System;using System.Collections.Generic;class GFG{// Structure of a tree nodeclass TreeNode { // Stores data value of a node public int data; // Stores left subtree // of a tree node public TreeNode left; // Stores right subtree // of a tree node public TreeNode right; // Initialization of // a tree node public TreeNode(int val) { // Update data data = val; // Update left and right left = right = null; }};// Function to check if a binary tree// is binary search tree or notstatic bool checkTreeIsBST(TreeNode root) { // Stores root node and left // subtree of each node Stack<TreeNode > Stack = new Stack<TreeNode >(); // Stores previous visited node TreeNode prev = null; // Traverse the binary tree while (Stack.Count!=0 || root != null) { // Traverse left subtree while (root != null) { // Insert root into Stack Stack.Push(root); // Update root root = root.left; } // Stores top element of Stack root = Stack.Peek(); // Remove the top element of Stack Stack.Pop(); // If data value of root node less // than data value of left subtree if(prev != null && root.data <= prev.data) { return false; } // Update prev prev = root; // Traverse right subtree // of the tree root = root.right; } return true;}// Driver Codepublic static void Main(String[] args){ /* 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 */ // Initialize binary tree TreeNode root = new TreeNode(9); root.left = new TreeNode(6); root.right = new TreeNode(10); root.left.left = new TreeNode(4); root.left.right = new TreeNode(7); root.right.right = new TreeNode(11); root.left.left.left = new TreeNode(3); root.left.left.right = new TreeNode(5); root.left.right.right = new TreeNode(8); if (checkTreeIsBST(root)) { Console.Write("YES"); } else { Console.Write("NO"); }}} // This code is contributed by shikhasingrajput |
Javascript
<script>// Javascript program to implement// the above approach// Structure of a tree nodeclass TreeNode{ constructor(val) { // Stores left subtree // of a tree node this.left = null; // Stores right subtree // of a tree node this.right = null; // Stores data value of a node this.data = val; }}// Function to check if a binary tree// is binary search tree or notfunction checkTreeIsBST(root){ // Stores root node and left // subtree of each node let Stack = []; // Stores previous visited node let prev = null; // Traverse the binary tree while (Stack.length > 0 || root != null) { // Traverse left subtree while (root != null) { // Insert root into Stack Stack.push(root); // Update root root = root.left; } // Stores top element of Stack root = Stack[Stack.length - 1]; // Remove the top element of Stack Stack.pop(); // If data value of root node less // than data value of left subtree if (prev != null && root.data <= prev.data) { return false; } // Update prev prev = root; // Traverse right subtree // of the tree root = root.right; } return true;}// Driver code/* 9 / \ 6 10 / \ \ 4 7 11 / \ \ 3 5 8 */ // Initialize binary treelet root = new TreeNode(9);root.left = new TreeNode(6);root.right = new TreeNode(10);root.left.left = new TreeNode(4);root.left.right = new TreeNode(7);root.right.right = new TreeNode(11);root.left.left.left = new TreeNode(3);root.left.left.right = new TreeNode(5);root.left.right.right = new TreeNode(8); if (checkTreeIsBST(root)) { document.write("YES");}else{ document.write("NO");}// This code is contributed by divyeshrabadiya07</script> |
Output:
YES
Time Complexity: O(N), where N is count of nodes in the binary tree
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
