Sharing answer codes of mine about HackerRank: Is This a Binary Search Tree.
HackerRank: Is this a Binary Search Tree (in Data Structures)
Problem Statement
For the purposes of this challenge, we define a binary tree to be a binary search tree with the following ordering requirements:
The data value of every node in a node’s left subtree is less than the data value of that node. The data value of every node in a node’s right subtree is greater than the data value of that node. Given the root node of a binary tree, can you determine if it’s also a binary search tree?
Complete the function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must return a boolean denoting whether or not the binary tree is a binary search tree. You may have to write one or more helper functions to complete this challenge.
Answer Code using Deque (in Python3)
- Time complexity: \(O(n)\) (\(n\) is the number of nodes)
""" Node is defined as
class node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
"""
from collections import deque
import math
def check_binary_search_tree_(root):
dq = deque([(root, -math.inf, math.inf)])
while dq:
node_now, minV, maxV = dq.popleft()
if node_now == None: continue
if node_now.data <= minV or node_now.data >= maxV: return False
if node_now.left: dq.append((node_now.left, minV, node_now.data))
if node_now.right: dq.append((node_now.right, node_now.data, maxV))
return True
Answer Code using Recursion (in Python3)
- Time complexity: \(O(n)\) (\(n\) is the number of nodes)
""" Node is defined as
class node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
"""
import math
visited = -math.inf
# Inorder traversal using recursive function
def check_binary_search_tree_(root):
global visited
if not root: return True
if not check_binary_search_tree_(root.left): return False
if root.data <= visited: return False
visited = root.data
if not check_binary_search_tree_(root.right): return False
return True
