Search In BST

Given a BST and an integer k. Find if the integer k is present in the given BST or not. You have to return true, if a node with data k is present, return false otherwise.

Note: Assume that BST contains all unique elements.

Input Format:
The first line of input contains data of the nodes of the tree in level order form. The data of the nodes of the tree is separated by space. If any node does not have left or right child, take -1 in its place. Since -1 is used as an indication whether the left or right nodes exist, therefore, it will not be a part of the data of any node.   
The following line of input contains an integer, that denotes the value of k.
Output Format:
The first and only line of output contains a boolean value. Print true, if node with data k is present, print false otherwise. 
Constraints:
Time Limit: 1 second
Sample Input 1 :
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
2
Sample Output 1 :
true
Sample Input 2 :
8 5 10 2 6 -1 -1 -1 -1 -1 7 -1 -1
12
Sample Output 2 :
false

 


import queue
class BinaryTreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def searchInBST(root, k):
if root is None:
return None
if k == root.data:
return root
if k < root.data:
return searchInBST(root.left, k)
if k > root.data:
return searchInBST(root.right, k)
def buildLevelTree(levelorder):
index = 0
length = len(levelorder)
if length<=0 or levelorder[0]==-1:
return None
root = BinaryTreeNode(levelorder[index])
index += 1
q = queue.Queue()
q.put(root)
while not q.empty():
currentNode = q.get()
leftChild = levelorder[index]
index += 1
if leftChild != -1:
leftNode = BinaryTreeNode(leftChild)
currentNode.left =leftNode
q.put(leftNode)
rightChild = levelorder[index]
index += 1
if rightChild != -1:
rightNode = BinaryTreeNode(rightChild)
currentNode.right =rightNode
q.put(rightNode)
return root
# Main
levelOrder = [int(i) for i in input().strip().split()]
root = buildLevelTree(levelOrder)
k=int(input())
node=searchInBST(root, k)
if node:
print("true")
else:
print("false")


Comments

Popular posts from this blog

MySQL Multi Source Master Slave Replication using GTID

Access and modify all the resources of our Wiki.js using WikiJS API

How to setup an Nginx reverse proxy with a SSL certificate in XWIKI