Handout #14 CSE205
Last Name (Print) First Name Lab ID
Binary Search Tree
1. Given the following binary tree (B-Tree). Answer each question.
1. The Root:
2. The Leaves:
3. Height of Tree:
4. Level of root node:
5. Nodes at level 1:
6. Parent of node 7:
2. Using the binary tree in the question above, answer the output of orders.
Pre-Order:
In-Order:
Post-Order:
3. Complete the insert (Object o) method for binary search tree (BST).
public class Handout14 {
private Node root;
//***** Inner class tree node ************
private class Node {
Object data;
Node left, right;
public Node(Object o){data = o;}
}//***************************************
public Handout14 (){ root = null;}
public boolean insert (Object o){
if (root == null) {root=new Node(o); return true;}
// locate the parent node
Node parent = null;
Node current = root;
while(current != null){
if(((Comparable)o).compareTo(current.data) < 0){
}
else if(((Comparable)o).compareTo(current.data) > 0){
}
else
}
//Create the new node and attach it to the parent node
if(((Comparable)o).compareTo(current.data) < 0)
else
return true;
}
4. Show the binary search tree that results when the following values are added, in order (added to the
BST from left to right), to a new tree. 14 20 8 9 69 2 4 56
Powered by TCPDF (www.tcpdf.org)
