# 1. Family Tree¶

The Family Tree is also a recursive data structure.

In :
class FamilyTree {
String name;
FamilyTree mother;
FamilyTree father;

FamilyTree(String name) {
this.name = name;
}

}

|  Added class FamilyTree


In :
FamilyTree me = new FamilyTree("Doug");

|  Added variable me of type FamilyTree with initial value FamilyTree@44e81672


In :
me.mother = new FamilyTree("Norma");
me.father = new FamilyTree("Scotty");

|  Expression value is: FamilyTree@6aceb1a5
|    assigned to temporary variable $3 of type FamilyTree | Expression value is: FamilyTree@ba4d54 | assigned to temporary variable$4 of type FamilyTree


Out:
FamilyTree@ba4d54
In :
System.out.println(me.name);

Doug


In :
System.out.println(me.father.name);

Scotty



## 1.1 Binary Trees¶

The data structure. We'll use this the same way that we did the LinkedList. That is we will have:

• Node class - keeps track of next, and data
• A BinaryTree class - has all methods, and head

For BinaryTrees we will use the terms left and right instead of next, and root instead of head.

class Node {
double data;
Node left;
Node right;

Node(double data) {
this.data = data;
}
}

class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
///
}
}
}


Consider adding the method add(Node) that would add nodes in no particular order. My natural instincts tell me to let the node do it:

class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
}
}
}


...and then have Node do it recursively... but...

class Node {
double data;
Node left;
Node right;

Node(double data) {
this.data = data;
}

if (left == null)
left = node;
else if (right == null)
right = node;
else {
/// what would go here?
}
}
}

In :
import java.lang.Math;

class Node {
double data;
Node left;
Node right;

Node(double data) {
this.data = data;
}

if (left == null)
left = node;
else if (right == null)
right = node;
else {
if (Math.random() < .5) {
} else {
}

}

}

}




In :
class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
}
}
}

|  Added class BinaryTree


In :
BinaryTree btree = new BinaryTree();

|  Added variable btree of type BinaryTree with initial value BinaryTree@2471cca7


In :
btree.add(new Node(23));


In :
btree.add(new Node(46));


How can we get some feedback about what is in the tree? We could print out the tree, but that is actually a bit difficult. Why?

First, let's find the "depth" of the tree:

In :
class BinaryTree {
Node root;

if (root == null) {
root = node;
} else {
}
}

public int depth() {
return depth(root);
}

public int depth(Node node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}
}

|  Replaced class BinaryTree
|    Update replaced variable btree, reset to null
|    Update overwrote class BinaryTree


In :
BinaryTree btree = new BinaryTree();

|  Modified variable btree of type BinaryTree with initial value BinaryTree@50675690


In :
btree.depth()

|  Expression value is: 0
|    assigned to temporary variable $15 of type int  Out: 0 In : btree.add(new Node(23));  In : btree.depth()  | Expression value is: 1 | assigned to temporary variable$17 of type int


Out:
1
In :
btree.add(new Node(46));


In :
btree.depth()

|  Expression value is: 2
|    assigned to temporary variable $19 of type int  Out: 2 In : btree.add(new Node(47)); btree.depth()  | Expression value is: 2 | assigned to temporary variable$21 of type int


Out:
2
In :
btree.add(new Node(47));
btree.depth()

|  Expression value is: 3
|    assigned to temporary variable $23 of type int  Out: 3 In : BinaryTree btree = new BinaryTree();  | Modified variable btree of type BinaryTree with initial value BinaryTree@5f150435  In : for (int i=0; i < 1000000; i++) { btree.add(new Node(i)); }  What do you think the depth is? btree.depth();  In : btree.depth();  | Expression value is: 23 | assigned to temporary variable$29 of type int


Out:
23

# Lab 3: Sorted Binary Tree¶

In :
class Node {
double data;
Node left;
Node right;

Node(double data) {
this.data = data;
}

if (node.data < this.data) {
if (this.left == null) {
this.left = node;
} else {
}
} else {
if (this.right == null) {
this.right = node;
} else {
}
}
}
}

|  Modified class Node
|    Update overwrote class Node


In :
class BinaryTree {
Node root;

public int depth() {
return depth(root);
}

public int depth(Node node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}

if (root == null) {
root = node;
} else {
}
}
}

|  Modified class BinaryTree
|    Update overwrote class BinaryTree


In :
BinaryTree btree = new BinaryTree();

|  Modified variable btree of type BinaryTree with initial value BinaryTree@f5f2bb7


In :
for (int i=0; i < 1000; i++) {
}


In :
BinaryTree btree = new BinaryTree();
for (int i=0; i < 1000000; i++) {
}

|  Modified variable btree of type BinaryTree with initial value BinaryTree@445b84c0


In :
btree.depth()

|  Expression value is: 50
|    assigned to temporary variable \$55 of type int


Out:
50

In [ ]:
class Node {
double data;
Node left;
Node right;

Node(double data) {
this.data = data;
}
}

In [ ]:
class BinaryTree {
Node root;

public int depth() {
return depth(root);
}

public int depth(Node node) {
if (node == null) {
return 0;
} else {
return 1 + Math.max(depth(node.left), depth(node.right));
}
}