Name:Naveen Kumar K
Q2
Given a binary tree, write code to determine whether the tree is complete. A
complete binary tree can only have missing nodes on the last level, and those
nodes must be in the leftmost positions.
program:
class TreeNode:
def --init--(self,val=0,left=None,right=None):
[Link]=val
[Link]=left
[Link]=right
def isCompletedTree(root):
if not root:
return True
queue=[root]
found_null=False
while queue:
node=[Link](0)
if node:
if found_null:
return False
[Link]([Link])
[Link]([Link])
else:
found-null=True
for n in queue:
if n:
return false
return True
root=TreeNode(1)
[Link]=TreeNode(2)
[Link]=TreeNode(3)
[Link]=TreeNode(4)
[Link]=TreeNode(5)
[Link]=TreeNode(6)
print(isCompleteTree(root))
Q3
Given a binary tree, validate that it is a binary search tree.
A Binary tree is a binary search tree if:
1. for each node, all nodes in the left sub-tree have strictly lower values
2. for each node, all nodes in the right sub-tree have strictly higher values
program:
class TreeNode:
def --init--(self,val=0,left=None,right=None):
[Link]=val
[Link]=left
[Link]=right
def isValid(root):
def inorder_traversal(node,inorder):
if not node:
return
inorder_traversal([Link],inorder)
[Link]([Link])
inorder_traversal([Link],inorder)
inorder=[]
inorder_traversal(root,inorder)
for i in range(1,len(inorder)):
if inorder[i]<=inorder[i-1]:
return False
return True
root=TreeNode(2)
[Link]=TreeNode(1)
[Link]=TreeNode(3)
print(isValid(root))