Implementing a Tree
How Do You Program a Tree?
In the following example:
- The tree data structure is represented by a ‘TreeNode’ struct which has a ‘value’ field to store the value of the node and a ‘children’ field to hold a collection of child nodes
- The ‘createTreeNode’ function is used to create a new tree node and initialise its value and an empty children collection
- The ‘addChild’ function is used to add a child to a parent node. It creates a new child node with the specified value and appends it to the ‘children’ collection of the parent node
- Then the ‘createTreeNode’ creates the root node and adds children to it using the ‘addChild’ function. This allows the build up of the tree structure with multiple levels and branches
Pseudocode
// Define the Tree Node structure
struct TreeNode {
value // The value stored in the node
children // A collection of child nodes
}
// Create a function to create a new tree node
function createTreeNode(value):
node = new TreeNode()
node.value = value
node.children = []
return node
// Create the root node of the tree
root = createTreeNode(rootValue)
// Add children to a node
function addChild(parentNode, childValue):
childNode = createTreeNode(childValue)
parentNode.children.append(childNode)
// Usage example:
addChild(root, childValue1)
addChild(root, childValue2)
addChild(root, childValue3)
// Add a child to an existing child node
addChild(root.children[0], grandchildValue)
// ...and so on
Python
# Define the Tree Node class
class TreeNode:
def __init__(self, value):
self.value = value
self.children = []
# Create a function to add a child to a node
def add_child(parent_node, child_value):
child_node = TreeNode(child_value)
parent_node.children.append(child_node)
# Create the root node of the tree
root_value = "Root" # Replace with the desired value
root = TreeNode(root_value)
# Add children to the root node
child_value1 = "Child 1" # Replace with the desired value
child_value2 = "Child 2" # Replace with the desired value
child_value3 = "Child 3" # Replace with the desired value
add_child(root, child_value1)
add_child(root, child_value2)
add_child(root, child_value3)
# Add a child to an existing child node
grandchild_value = "Grandchild" # Replace with the desired value
add_child(root.children[0], grandchild_value)
# Usage example:
print(root.value) # Output: "Root"
print(root.children[0].value) # Output: "Child 1"
print(root.children[0].children[0].value) # Output: "Grandchild"
Java
import java.util.ArrayList;
import java.util.List;
// Define the Tree Node class
class TreeNode {
String value;
List<TreeNode> children;
TreeNode(String value) {
this.value = value;
this.children = new ArrayList<>();
}
}
public class TreeExample {
public static void main(String[] args) {
// Create the root node of the tree
String rootValue = "Root";
TreeNode root = new TreeNode(rootValue);
// Add children to the root node
String childValue1 = "Child 1";
String childValue2 = "Child 2";
String childValue3 = "Child 3";
addChild(root, childValue1);
addChild(root, childValue2);
addChild(root, childValue3);
// Add a child to an existing child node
String grandchildValue = "Grandchild";
addChild(root.children.get(0), grandchildValue);
// Usage example:
System.out.println(root.value);
// Output: "Root"
System.out.println(root.children.get(0).value);
// Output: "Child 1"
System.out.println(root.children.get(0).children.get(0).value);
}
// Create a method to add a child to a node
public static void addChild(TreeNode parentNode, String childValue) {
TreeNode childNode = new TreeNode(childValue);
parentNode.children.add(childNode);
}
}
Algorithm to Traverse a Tree
Post Order Traversal
- Post-Order traversal follows the order:
- Left Subtree
- Right Subtree
- Root Node
- Using the outline method, nodes are traversed in the order in which you pass them on the right
- You can recap the theory notes on Tree Data Structures here
- Note: The algorithm below shows that this is identical to the other methods of traversing a tree (pre-order and in-order) except for the position of the output statement. You do not require the other two methods for OCR
- Node is an object with 3 attributes; node.data contains a value, node.left contains a pointer to the left child node and node.right contains a pointer to the right child node
- As mentioned above, the algorithm will traverse the left subtree, then the right subtree then the root
Pseudocode
PROCEDURE post_order_traversal(node)
// Check any nodes to the left of the current node
IF node.left != Null THEN
post_order_traversal(node.left)
ENDIF
// Check any nodes to the right of the current node
IF node.right != Null THEN
post_order_traversal(node.right)
ENDIF
// Output the data of the current node
PRINT(node.data)
ENDPROCEDURE
Python
def post_order_traversal(node):
# Check any nodes to the left of the current node
if node.left is not None:
post_order_traversal(node.left)
# Check any nodes to the right of the current node
if node.right is not None:
post_order_traversal(node.right)
# Output the data of the current node
Java
class Node {
int data;
Node left;
Node right;
}
class Tree {
Node root;
}
public class PostOrderTraversal {
public static void postOrderTraversal(Node node) {
if (node != null) {
// Check any nodes to the left of the current node
if (node.left != null) {
postOrderTraversal(node.left);
}
// Check any nodes to the right of the current node
if (node.right != null) {
postOrderTraversal(node.right);
}
// Output the data of the current node
System.out.println(node.data);
}
}
public static void main(String[] args) {
// Create a sample tree
Tree tree = new Tree();
tree.root = new Node();
tree.root.data = 1;
tree.root.left = new Node();
tree.root.left.data = 2;
tree.root.right = new Node();
tree.root.right.data = 3;
// Perform post-order traversal on the tree
postOrderTraversal(tree.root);
}
}
Algorithm to Add Data to a Tree
- In your exam, the exam board quite often uses binary trees in their questions. The algorithm below will use a binary tree for that reason.
- The code defines a binary tree and a function to add a new node to the tree.
- The binary tree is represented using a class called ‘Node’, where each node has a data value, a left child, and a right child.
- The add_node function takes two parameters: the root of the binary tree and the value of the new node to be added.
- If the tree is empty (root is ‘None’), it creates a new node with the given value and sets it as the root.
- Otherwise, it performs a traversal using a queue to find the first available position (either the left or right child of a node) to insert the new node.
Pseudocode
NODE:
data: INTEGER
left: NODE
right: NODE
FUNCTION add_node(tree, value):
new_node = NODE()
new_node.data = value
IF tree IS NULL:
tree = new_node
ELSE:
current = tree
WHILE True:
IF value < current.data:
IF current.left IS NULL:
current.left = new_node
BREAK
ELSE:
current = current.left
ELSE:
IF current.right IS NULL:
current.right = new_node
BREAK
ELSE:
current = current.right
ENDFUNCTION
Python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def add_node(root, value):
if root is None:
root = Node(value)
else:
queue = []
queue.append(root)
while len(queue) > 0:
current = queue.pop(0)
if current.left is None:
current.left = Node(value)
break
else:
queue.append(current.left)
if current.right is None:
current.right = Node(value)
break
else:
queue.append(current.right)
return root
# Example usage
root = Node(1)
root.left = Node(2)
root.right = Node(3)
print("Before adding node:")
# Perform pre-order traversal to display the tree before adding the node
def pre_order_traversal(node):
if node is not None:
print(node.data, end=" ")
pre_order_traversal(node.left)
pre_order_traversal(node.right)
pre_order_traversal(root)
print()
root = add_node(root, 4)
print("After adding node:")
pre_order_traversal(root)
Java
import java.util.LinkedList;
import java.util.Queue;
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
Node root;
public void addNode(int value) {
if (root == null) {
root = new Node(value);
} else {
Queue<Node> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
Node current = queue.poll();
if (current.left == null) {
current.left = new Node(value);
break;
} else {
queue.offer(current.left);
}
if (current.right == null) {
current.right = new Node(value);
break;
} else {
queue.offer(current.right);
}
}
}
}
// Example usage
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
System.out.println("Before adding node:");
// Perform pre-order traversal to display the tree before adding the node
preOrderTraversal(tree.root);
System.out.println();
tree.addNode(4);
System.out.println("After adding node:");
preOrderTraversal(tree.root);
}
// Pre-order traversal method to display the tree
public static void preOrderTraversal(Node node) {
if (node != null) {
System.out.print(node.data + " ");
preOrderTraversal(node.left);
preOrderTraversal(node.right);
}
}
}
Algorithm to Remove Data from a Tree
- Once again, the algorithm below will use a binary tree
- The find_node function is a function that searches for a node with a given value in the tree.
- The remove_node function removes a node with a specified value from the tree, handling three cases:
- Node has no children (Leaf Node):
- Remove the node from the tree by setting it to ‘None’.
- Node has one child:
- Replace the node with its only child.
- Node has two children:
- Find the minimum value node in the right subtree (or the maximum value node in the left subtree).
- Replace the node’s data with the data of the replacement node.
- Recursively remove the replacement node.
- Node has no children (Leaf Node):
- The find_minimum function is a function that helps to find the node with the minimum value in a given subtree.
Pseudocode
NODE:
data: INTEGER
left: NODE
right: NODE
FUNCTION find_node(tree, item):
IF tree IS NULL:
RETURN NULL
ELSE IF tree.data == item:
RETURN tree
ELSE IF item < tree.data:
RETURN find_node(tree.left, item)
ELSE:
RETURN find_node(tree.right, item)
ENDIF
FUNCTION remove_node(tree, item):
node = find_node(tree, item)
IF node IS NULL:
PRINT("Item not found in the tree")
ELSE:
IF node.left IS NULL AND node.right IS NULL:
// Case 1: Node has no children
// Simply remove the node from the tree
DELETE node
ELSE IF node.left IS NULL OR node.right IS NULL:
// Case 2: Node has only one child
// Replace the node with its child
IF node.left IS NOT NULL:
child = node.left
ELSE:
child = node.right
ENDIF
UPDATE_PARENT(node, child)
DELETE node
ELSE:
// Case 3: Node has two children
// Find the replacement node (either minimum value in right subtree or maximum value in left subtree)
replacement = find_minimum(node.right)
node.data = replacement.data
remove_node(node.right, replacement.data)
ENDIF
ENDIF
ENDFUNCTION
Python
class Node:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
def find_node(tree, item):
if tree is None:
return None
elif tree.data == item:
return tree
elif item < tree.data:
return find_node(tree.left, item)
else:
return find_node(tree.right, item)
def remove_node(tree, item):
node = find_node(tree, item)
if node is None:
print("Item not found in the tree")
else:
if node.left is None and node.right is None:
# Case 1: Node has no children
# Simply remove the node from the tree
node = None
elif node.left is None or node.right is None:
# Case 2: Node has only one child
# Replace the node with its child
if node.left is not None:
child = node.left
else:
child = node.right
node.data = child.data
node.left = child.left
node.right = child.right
else:
# Case 3: Node has two children
# Find the replacement node (minimum value in right subtree)
replacement = find_minimum(node.right)
node.data = replacement.data
remove_node(node.right, replacement.data)
def find_minimum(node):
while node.left is not None:
node = node.left
return node
# Example usage
tree = Node(4)
tree.left = Node(2)
tree.right = Node(6)
tree.left.left = Node(1)
tree.left.right = Node(3)
tree.right.left = Node(5)
tree.right.right = Node(7)
remove_node(tree, 2)
Java
class Node {
int data;
Node left;
Node right;
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
class BinaryTree {
Node root;
public Node findNode(Node tree, int item) {
if (tree == null) {
return null;
} else if (tree.data == item) {
return tree;
} else if (item < tree.data) {
return findNode(tree.left, item);
} else {
return findNode(tree.right, item);
}
}
public void removeNode(Node tree, int item) {
Node node = findNode(tree, item);
if (node == null) {
System.out.println("Item not found in the tree");
} else {
if (node.left == null && node.right == null) {
// Case 1: Node has no children
// Simply remove the node from the tree
node = null;
} else if (node.left == null || node.right == null) {
// Case 2: Node has only one child
// Replace the node with its child
Node child = (node.left != null) ? node.left : node.right;
node.data = child.data;
node.left = child.left;
node.right = child.right;
} else {
// Case 3: Node has two children
// Find the replacement node (minimum value in right subtree)
Node replacement = findMinimum(node.right);
node.data = replacement.data;
removeNode(node.right, replacement.data);
}
}
}
public Node findMinimum(Node node) {
while (node.left != null) {
node = node.left;
}
return node;
}
// Example usage
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
tree.root = new Node(4);
tree.root.left = new Node(2);
tree.root.right = new Node(6);
tree.root.left.left = new Node(1);
tree.root.left.right = new Node(3);
tree.root.right.left = new Node(5);
tree.root.right.right = new Node(7);
tree.removeNode(tree.root, 2);
}
}