Section 14
Binary Tree Modification
CSE 123 - Spring 2023 || Fall 2023
Section AK || Section AA
Section 14 - Spring 2023
Agenda
Section 14 - Spring 2023
Announcements and Discussion (5 min)
01
Review (10 min)
02
Practice! (35 min)
03
Section 14 - Spring 2023
Discussion
01
Discussion Questions
Feel free to head over to Ed and enter your responses there!�Find a partner to discuss with too!
Given the following binary search tree, what is one possible ordering that the elements need to be inserted in order to produce this exact tree?
Below is one student's attempt at writing a method insertLeftLeaf() that adds a new leaf node to the given binary tree in the leftmost position.
However, after calling insertLeftLeaf() on an existing binary tree, the student notices that the tree remains unchanged.�Debug this program! What does the student need to add to their code for the method to correctly add a new IntTreeNode in the leftmost position?
Section 14 - Spring 2023
Section 14 - Spring 2023
Binary Search Tree
02
Binary Search Trees
Section 14 - Spring 2023
A Binary Search Tree (BST) is a binary tree with a special sorting property.
BST Conventions:
Motivation:
The following visualizations show some valid BST to represent a list of integers [1, 2, 3, 4, 5, 6].
x = change(x)
Section 14 - Spring 2023
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
public void add(int value) {
add(overallRoot, value);
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
x = change(x)
Section 14 - Spring 2023
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
public void add(int value) {
add(overallRoot, value);
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
Section 14 - Spring 2023
change Version 1
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
overallRoot
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
4
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
}
root
4
Oh no! The tree was never modified! 😭😱😨😩🥴
Let’s fix this.
Section 14 - Spring 2023
change Version 2
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value); // value = 4
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
overallRoot
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
add(overallRoot, value); // value = 4
}�
private void add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
add(root.left, value);
} else {
add(root.right, value);
}
return root;
}
root
4
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
root
4
add
Section 14 - Spring 2023
Goal: Add a node storing the value 4 in this tree�
public void add(int value) {
overallRoot = add(overallRoot, value);
}�
private IntTreeNode add(IntTreeNode root,� int value) {
if (root == null) {
root = new IntTreeNode(value);
} else if (value < root.data) {
root.left = add(root.left, value);
} else {
root.right = add(root.right, value);
}
return root;
}
overallRoot
4
Tips for Binary Tree Modification
Section 14 - Spring 2023
[Starter Programming Problem]
Section 14 - Spring 2023
Remove Leaves
🌿
[Complex Programming Problem]
Section 14 - Spring 2023
Read Tree [Helpful for BrettFeed]
📝
[Starter Programming Problem]
Section 14 - Spring 2023
Complete ToLevel [if time]
🌿
THANKS!
See you next section!
Reach out to me with any questions :)