Trees (OCR A Level Computer Science)

Revision Note

Written by: Jennifer Page

Reviewed by: James Woodhouse

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);

// Output: "Grandchild"

}

// 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.
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

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);

}

Last updated: 12 September 2024

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

the (exam) results speak for themselves:

Did this page help you?

Previous:Linked Lists

Trees (OCR A Level Computer Science)

Revision Note

Implementing a Tree

How Do You Program a Tree?

Algorithm to Traverse a Tree

Post Order Traversal

Algorithm to Add Data to a Tree

Algorithm to Remove Data from a Tree

You've read 0 of your 10 free revision notes

Unlock more, it's free!

Join the 100,000+ Students that ❤️ Save My Exams

Author: Jennifer Page

Author: James Woodhouse