Question

2 Binary Search Trees- 10 points (5 points each) 1. Write pseudocode for an algorithm that takes in the root of a binary tree and returns whether or not the tree is a legal binary search tree. 2. Write pseudocode for an algorithm that takes in the root of a binary search tree and prints the keys in sorted order.

please I need it urgent thanks algorithms

Answer 1

1.

FUNCTION İSVALID (NODE ROOT) 1 //if root is empty, tree is legal IF ROOT NULL RETURİ TRUE //if left child is greater than root, or right child is lower than root, it 1s invalid IF ROOT.LEFT.VAL ROOT.VAL OR ROOT.RIGHT.VALKROOT.VAL RETURN FALSE //Check left subtree LEFT VALIDISVALID (ROOT. LEFT) //Check right subtree RIGHT_VALID ISVALID (ROOT.RIGHT) //See if both the subtrees are valid 10 12 13

FUNCTION ISVALID(NODE ROOT)
   //if root is empty, tree is legal
   IF ROOT==NULL
       RETURN TRUE
   //if left child is greater than root, or right child is lower than root, it is invalid
   IF ROOT.LEFT.VAL>ROOT.VAL OR ROOT.RIGHT.VAL<ROOT.VAL
       RETURN FALSE
   //Check left subtree
   LEFT_VALID = ISVALID(ROOT.LEFT)
   //Check right subtree
   RIGHT_VALID = ISVALID(ROOT.RIGHT)
   //See if both the subtrees are valid
   RETURN LEFT_VALID AND RIGHT_VALID

2.

FUNCTION INORDER (NODE ROOT) /lif root is empty, return IF ROOT==NULL RETURN //Traverse left subtree INORDER (ROOT.LEFT) //Prin the root PRINT (ROOT.VAL) 9//Traverse right subtree INORDER (ROOT.RIGHT) 10

FUNCTION INORDER(NODE ROOT)
   //if root is empty, return
   IF ROOT==NULL
       RETURN
   //Traverse left subtree
   INORDER(ROOT.LEFT)
   //Prin the root
   PRINT(ROOT.VAL)
   //Traverse right subtree
   INORDER(ROOT.RIGHT)