BST Tree Traversals

A visual review of BST and its traversal techniques. Thanks to tree visualizer and Wikipedia's article on Tree Traversal.

26 flashcards · Computer Science · by kgashok

1. Inorder traversal of a BST will produce what output?

   [7, 29, 40, 41, 44, 50, 53, 67, 84, 97] Inorder of BST will produce a sorted ascending order. Also, a Reverse Inorder of BST will produce a sorted descending order.

2. The output of an inorder traversal of a BST tree was [1, 2, 3, 4, 5, 6, 7]. The output of a postorder traversal of the same tree produces [7, 6, 5, 4, 3, 2, 1] Do you know what the BST looks like?

3. The output of an inorder traversal of a balanced and complete BST tree was [1, 2, 3, 4, 5, 6, 7]. What does the tree look like?

4. The preorder of a BST will match the order in which the nodes were inserted into the data structure. True or False?

   True

5. The level order of a complete binary tree is [5, 1, 7, 0, 2, 6, 8] Does that make the binary tree a BST?

   Yes. Level Order means the order in which the elements occur in the tree from root to leaves, level-wise, left to right.

6. # A class that represents an individual node in a # Binary Tree class Node: def __init__(self,key): self.left = None self.right = None self.val = key True or False?

   True

7. def mysteryorder(node): if node: # First recur on left child mysteryorder(node.left) # then print the data of node print(node.val, end=" ") # now recur on right child mysteryorder(node.right) The above code represents what type of traversal? A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

   Choice A. Left -> Node -> Right (LNR) depth search is in-order traversal.

8. Write the recursive pseudo code for in-order traversal (LNR).

9. Write the iterative pseudo code (using a stack) for in-order traversal.

10. Write iterative in-order traversal in Python.

    def inorder(node): result = [] stack = [] while stack or node: if node is not None: stack.append(node) node = node.left else: node = stack.pop() result.append(node) node = node.right return result

11. def mysteryorder(node): if node: # First print the data of node print(node.val) # Then recur on left child mysterorder(node.left) # Finally recur on right child mysteryorder(node.right) The above code represents what type of traversal? A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

    Choice B. Node -> Left -> Right (NLR) depth search is pre-order traversal.

12. Write a pre-order traversal of a binary tree in Python.

    node_stack = [self] result = [] while len(node_stack) > 0: node = node_stack.pop() result.append(node) if node.right is not None: node_stack.append(node.right) if node.left is not None: node_stack.append(node.left) return result

13. def mysteryorder(node): if node: # First recur on left child mysteryorder(node.left) # the recur on right child mysteryorder(node.right) # now print the data of node print(node.val) The above code represents what type of traversal? A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

    Choice D Left -> Right -> Node (LRN) depth search is post-order traversal.

14. mysteryorder(node) if (node == null) return mysteryorder(node.left) mysteryorder(node.right) visit(node) The above pseudo code represents what type of traversal? A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

    Choice D.

15. Write a post-order traversal of a binary tree in Python.

    node_stack = [] result = [] node = self while True: while node is not None: if node.right is not None: node_stack.append(node.right) node_stack.append(node) node = node.left node = node_stack.pop() if (node.right is not None and len(node_stack) > 0 and node_stack[-1] is node.right): node_stack.pop() node_stack.append(node) node = node.right else: result.append(node) node = None if len(node_stack) == 0: break return result

16. The above traversal diagram is referred to as A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

    Choice E.

17. mysteryorder(root) q ← empty queue q.enqueue(root) while not q.isEmpty() do node ← q.dequeue() visit(node) if node.left ≠ null then q.enqueue(node.left) if node.right ≠ null then q.enqueue(node.right) The above pseudo code represents what type of traversal? A. in-order (LNR) B. pre-order (NLR) C. reverse-in-order (RNL) D. post-order (LRN) E. level-order

    Choice E. Iterative level-order traversal requires a queue to be efficient.

18. You need to Generate a suitable expression for evaluating a binary expression tree. Delete and free up all the nodes in a binary tree. Duplicate a binary tree. Choose the appropriate traversal technique for each of the above cases.

    Post-order (LRN) traversal is ideal for first two applications. Try the D.H. Expert: Evaluate the Tree in 100DaysChallenge repl.it classroom. Pre-order (NLR) traversal is ideal for duplicating or cloning a binary tree.

19. Write a iterative level-order traversal in Python.

    current_nodes = [self] result = [] while len(current_nodes) > 0: next_nodes = [] for node in current_nodes: result.append(node) if node.left is not None: next_nodes.append(node.left) if node.right is not None: next_nodes.append(node.right) current_nodes = next_nodes return result

20. Write the python function that returns a list that contains the minimum value and the maximum value in a BST tree.

    def minmax(root): node = root # traverse to far left for minimum while node.left: node = node.left res = [node.value] # traverse to far right for maximum node = root while node.right: node = node.right res.append(node.value) return res

21. Write the code whether the given tree is a valid binary search tree.

    class node: def __init__(self, data): self.data = data self.left = None self.right = None INT_MAX = 4294967296 INT_MIN = -4294967296 # Returns true if the given tree # is a binary search tree def check_binary_search_tree_(node): return (isBSTUtil(node, INT_MIN, INT_MAX)) # Return true if the given tree is a BST # and its values >= min and <= max def isBSTUtil(node, mini, maxi): # An empty tree is BST if node is None: return True # False if this node violates min/max constraint # if node.data <…

22. The above tree is a valid BST. True or False?

    False. 5 is less than 10. And therefore cannot be on the right side of the tree.

23. Binary Tree is a specialized form of tree with no more than two child (left child and right Child) nodes. It is simply representation of data in Tree structure. Binary Search Tree (BST) is a special type of Binary Tree that follows following condition: left child node is smaller than its parent Node right child node is greater than its parent Node True or False?

    False. The entire left subtree must contain keys only less than the parent's, and the entire right subtree must contain nodes greater than the parent's. See http://j.mp/verifyBST for more clarity.

24. The above binary tree is a Invalid, Incomplete, Imbalanced BST Invalid, Complete, Imbalanced BST Valid, Complete, Balanced BST Is a binary tree, but not BST

    Choice 3. It is valid, because the BST constraints are met. It is complete (full), because all nodes have two children. It is balanced because both sides of the root node have equal number of nodes.

25. You are asked to use an existing binary tree to generate a binary search tree (BST). you have access to a node root which is the root node of a valid binary tree. you have access to a function is_valid(root) which will return true if the node represents the root of a valid BST. you have access to a function preorder(root) which will accept the root node of a valid BST and will return a list containing the values in the nodes as per the preorder traversal of the tree. you also have access to a f…

    alist = preorder(root) alist.sort() bbst = build_balanced_bst(alist) # assert is_valid(bbtree) print("generated bbst", bbst)

26. In Ancient Greece, it was common to write text with the first line going left to right, the second line going right to left, and continuing to go back and forth. This style was called "boustrophedon". Given a binary tree, write an algorithm to print the nodes in boustrophedon order. For example, given the following tree: 1 / \ 2 3 / \ / \ 4 5 6 7 You should return [1, 3, 2, 4, 5, 6, 7]. Write the code for boustrophedon ordering of a tree.

    def boustrophedon_order(root): level = [] # intermediary level values result = [] # accumulates values for all levels q = [root] levelnum = 1 while q: count = len(q) while count: node = q.pop(0) if node: level.append(node.data) q.extend([node.left, node.right]) count -= 1 result = result + ( level if levelnum % 2 else \ level[::-1]) level.clear() levelnum += 1 return result