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


Tags:

Categories:

Updated: