Homework 7: Trees

Question 1:

Given the root of a binary tree, return the sum of all left leaves, your method signature should be as follows:

int sumOfLeftLeaves(BTNode root)

Question 2:

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the

values of the nodes in the tree. For the following BST and k=3, the expected output is 4.

Question 3:

Write the following method List> levelOrder(BTNode root), which, given the

root of a binary tree, will return the level order traversal of its nodes' values. (i.e., from left to right, level by

level). For the following binary tree, the output list should be: [[3],[9,20],[15,7]]

Question 4:

In the lab, we studied different algorithms for recursively traversing trees. Write an algorithm to do inorder

traversal iteratively.

Question 5:

Inorder Successor of a node in binary tree is the next node in inorder traversal of the binary tree. Inorder

Successor is NULL for the last node in Inorder traversal.

In the binary tree in question 3, 20 is the inorder successor of node 15, 15 is the inorder successor of 3.

Complete the following method to get the inorder successor node :

BTNode findInorderRecursive(BTNode root, BTNode node)

Question 6:

A full binary tree is defined as a binary tree in which all nodes have either zero or two child nodes. Write

implementation for boolean isFull(BTNode root) which will check if the binary tree is full or not.