Verify that a binary search tree is indeed a binary search tree.

Question

Friend · Accepted Answer

The idea is if we traverse binary search tree "in-order", output of number is in ascending orders.
So here it goes. Not checked for syntax errors, but should work.

BOOL Inorder(NODE *node)
{	
	static NODE *prev = NULL;   // Do need to initialize this as statics are zeroed memory.

	if (node == NULL) {
		return true;
	}
	if (false == Inorder(node->left)) {
		return false;
	}
	if (prev && node->num num) {
		return false;
	}
	prev = node;
	return Inorder(node->right);
}

Ashish Kaila · Answer

A simpler approach is to do an inorder traversal keeping track of last seen element. If it is always increasing then we can prove that tree is BST.

Anonymous · Answer

class TreeNode {
  var value: Int?
  var leftChild: TreeNode?
  var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
  print("value: " + String(node.value!))
  print("min: " + String(min))
  print("max: " + String(max))

  if node.value!  max 
  {
      return false
  }
  
  if let leftChild = node.leftChild {
     if isBST(leftChild, min: min, max: node.value!) == false {
       return false
     }
  }
  
  if let rightChild = node.rightChild {
     if isBST(rightChild, min: node.value!, max: max) == false {
       return false
     }
  }

  return true
}

// Creating BST
let minValue = Int.min  
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
  print("Tree is BST.")
}else {
   print("Tree is not BST.") 
}

Gus · Answer

Principle. Every node in a binary tree must have left node value  parent node

Bool checknode(node)
{
   If node.left then
   {
      If node.left.value > node.value then
          Return false
      If checknode(node.left) == false then
          Return false
   }
   If node.right then
   {
      If node.right.value < node.value then
          Return false
      If checknode(node.right) == false then
          Return false
   }
   Return true
}

Rahul · Answer

public static boolean isBST(Node n)
{
	if (null == n) return true;
	return (null != isBSTI(n));
}

public static ArrayList isBSTI(Node n)
{
	int min = n.val;
	int max = n.val;
	if (left != null)
	{
		ArrayList leftR = isBST(n.left);
		if (leftR.get(1) > val) return null;
		min = leftR.get(0);
	}
	if (right != null)
	{
		ArrayList rightR = isBST(n.right);
		if (rightR.get(0) (Arrays.asList(new Integer[] { min, max }));
}

@Testing · Answer

class TreeNode {
  var value: Int?
  var leftChild: TreeNode?
  var rightChild: TreeNode?
}

func isBST(node: TreeNode, min: Int, max: Int) -> Bool {
  print("value: " + String(node.value!))
  print("min: " + String(min))
  print("max: " + String(max))

  if node.value!  max 
  {
      return false
  }
  
  if let leftChild = node.leftChild {
     if isBST(leftChild, min: min, max: node.value!) == false {
       return false
     }
  }
  
  if let rightChild = node.rightChild {
     if isBST(rightChild, min: node.value!, max: max) == false {
       return false
     }
  }

  return true
}

// Creating BST
let minValue = Int.min  
let maxValue = Int.max

let node2 = TreeNode()
node2.value = 2
node2.leftChild = nil
node2.rightChild = nil

let node7 = TreeNode()
node7.value = 7
node7.leftChild = nil
node7.rightChild = nil

let node11 = TreeNode()
node11.value = 11
node11.leftChild = nil
node11.rightChild = nil

let node15 = TreeNode()
node15.value = 15
node15.leftChild = nil
node15.rightChild = nil

let node5 = TreeNode()
node5.value = 5
node5.leftChild = node2
node5.rightChild = node7

let node13 = TreeNode()
node13.value = 13
node13.leftChild = node11
node13.rightChild = node15

let node10 = TreeNode()
node10.value = 10
node10.leftChild = node5
node10.rightChild = node13

if isBST(node10, min: minValue, max: maxValue) == true {
  print("Tree is BST.")
}else {
   print("Tree is not BST.") 
}

cb · Answer

boolean isBST(Node root)
{
	if (root == null) return true;
	if ((root.left != null && root.data  root.right.data)) {
		return false;
	}
	return isBST(root.left) && isBST(root.right);
}

Ker · Answer

private static boolean isReallyBST(Node root) {
		return followsBST(root.left, root.value, true)
				&& followsBST(root.right, root.value, false);
	}

	private static boolean followsBST(Node node, Integer parent,
			boolean isLeft) {
		if (node == null) {
			return true;
		}

		boolean follows = isLeft ? node.value = parent;
		return follows && followsBST(node.left, node.value, true)
				&& followsBST(node.right, node.value, false);
	}

Farid · Answer

All the above answers, except the in-order traversal technique, are incorrect. The correct solution is as follows:

`
func isBSTHelper(min: Int, max: Int, tree: TreeNode?) -> Bool {
    guard let tree = tree else {
        return true
    }

    if tree.value = max {
        return false
    }

    return isBSTHelper(min: min, max: tree.value, tree: tree.left) && isBSTHelper(min: tree.value, max: max, tree: tree.right)

}
func isBST(_ t: TreeNode) -> Bool {
    return isBSTHelper(min: Int.min, max: Int.max, tree: t)
}

// example: 
let tree = ...
isBST(tree)
`

Matteo Gobbi · Answer

Very simple and efficient way:

public static boolean isBinaryTree(TreeNode root) {
        if(root == null) return true;
        
        if(!((root.rightSon == null || root.value  root.leftSon.value)))
            return false;
        
        if(!(root.rightSon == null || isBinaryTree(root.rightSon)))
            return false;
        
        if(!(root.leftSon == null || isBinaryTree(root.leftSon)))
            return false;
        
        return true;
    }


This is the class TreeNode in java:

class TreeNode
{
    public int value;
    public TreeNode rightSon;
    public TreeNode leftSon;
    
    public TreeNode(int value, TreeNode rightSon, TreeNode leftSon) {
        this.value = value;
        this.rightSon = rightSon;
        this.leftSon = leftSon;
    }
};


you can try with this example:



        //Decide if is a binary tree
        TreeNode tree = new TreeNode(15,new TreeNode(18,new TreeNode(22,new TreeNode(30,null,null),new TreeNode(21,null,null)),new TreeNode(16,null,null)),
                                     new TreeNode(10,new TreeNode(12,new TreeNode(13,null,null),new TreeNode(11,null,null)),new TreeNode(8,null,null)));
        boolean res = isBinaryTree(tree);
        
        System.out.println("Result: " + res);

//EXAMPLE:
//                         15
//                  10            18
//                8    12      16    22
//                   11  13        21  30
//

Anonymous · Answer

func isIndeeBST(root: Node?) -> Bool {
    if root == nil {
        return true
    }
    
    if root.left != nil && root.right != nil {
        if root.left?.value > root.right?.value {
            return false
        }
    }
    
    if root.left != nil {
        if root.left?.value > root.value {
            return false
        }
    }
    if root.right != nil {
        if root.right?.value < root.value {
            return false
        }
    }
    
    return isIndeeBST(root.left) & isIndeeBST(root.right)
}

Pavel · Answer

4
        2       6           =>    YES
      1   3   5   7

            4
        2       6 .         => NO
      1   3   3   7    


class TreeNode {

    var data: Int
    var left: TreeNode?
    var right: TreeNode?

    public init(_ val: Int) {
        self.val = val
        self.left = nil
        self.right = nil
    }
}

class Solution {

    func isValidBST(_ root: TreeNode?) -> Bool {
        return isValidBST(root, min: Int.min, max: Int.max)
    }

    func isValidBST(_ root: TreeNode?, min: Int, max: Int) -> Bool {
        guard root != nil else {
            return true
        }

        if root!.data  max {
            return false
        }

        return isValidBST(root?.left, min: min, max: root!.data - 1) &&
               isValidBST(root?.right, min: root!.data + 1, max: max)
    }
}

Meta

Meta interview question

Interview Answers

Followed companies

Job searches

Bowls

Want the inside scoop on your own company?