CSE 214 Computer Science II (Spring 2015)

RECITATION 9 – Binary Tree

Objective:

1. To Study Tree data structure
2. Perform a tree traversal

1. [10 min] Consider the following expressions:

Represent the expression in the form of a tree and write the pre-order and post-order traversal.

1. (((5+2)*(2-1))/((2+9)+((7-2)-1))*8)
2. P*Q –(R+S)*(X/Y)

2. [10 min]  Write a recursive method to find the minimum value in a binary search tree. This method will return the lowest integer value in the tree. When the function is called, the root of the tree is passed as the argument to the function, and it returns the integer value of the smallest element in the binary search tree. You may assume that the nodes have all necessary access and modifier methods.

3. [15 min]  Describe an algorithm, relying only on the BinaryTree operations, that counts the number of leaves in a binary tree that are the left child of their respective parent.

4. [15 min] Give the code for array implementation of the Binary search tree.

Write functions to carry out inorder, preorder traversal.

          [link: http://www3.cs.stonybrook.edu/~sael/teaching/cse214/rec/BinaryTree.java]