Revision NotesExam QuestionsPast Papers
A LevelComputer ScienceOCRRevision Notes8. Algorithms8.2 Algorithms for the Main Data StructuresTrees

Trees (OCR A Level Computer Science)

Revision Note

Jennifer Page

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:

  1. Left Subtree

  2. Right Subtree

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

  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:

You've read 0 of your 5 free revision notes this week

Sign up now. It’s free!

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

the (exam) results speak for themselves:

    Test yourself

    Did this page help you?

    Previous:Linked Lists
    Author
    Reviewer
    Jennifer Page

    Author: Jennifer Page

    Expertise: Computer Science

    Jennifer has been teaching various Computing subjects for over 6 years in Northamptonshire across KS3-5. Working currently as a Head of Department as well as being an examiner and moderator for GCSEs. She has previously worked with a local teaching training school to provide training and mentor ECTs in Computing.

    James Woodhouse

    Author: James Woodhouse

    Expertise: Computer Science

    James graduated from the University of Sunderland with a degree in ICT and Computing education. He has over 14 years of experience both teaching and leading in Computer Science, specialising in teaching GCSE and A-level. James has held various leadership roles, including Head of Computer Science and coordinator positions for Key Stage 3 and Key Stage 4. James has a keen interest in networking security and technologies aimed at preventing security breaches.