Binary Trees (Cambridge (CIE) A Level Computer Science): Revision Note

Node

An item in a tree

Edge

Connects two nodes together and is also known as a branch or pointer

Root

A single node which does not have any incoming nodes

Child

A node with incoming edges

Parent

A node with outgoing edges

Subtree

A subsection of a tree consisting of a parent and all the children of a parent

Leaf

A node with no children

Traversing

The process of visiting each node in a tree data structure, exactly once

CLASS TreeNode
    DECLARE value : STRING
    DECLARE children : ARRAY OF TreeNode
ENDCLASS

FUNCTION createTreeNode(val : STRING) RETURNS TreeNode
    DECLARE node : TreeNode
    SET node = NEW TreeNode
    SET node.value = val
    SET node.children = []
    RETURN node
ENDFUNCTION

PROCEDURE addChild(parent : TreeNode, childValue : STRING)
    DECLARE childNode : TreeNode
    SET childNode = createTreeNode(childValue)
    APPEND childNode TO parent.children
ENDPROCEDURE

// Example usage
DECLARE root : TreeNode
SET root = createTreeNode("Root")

CALL addChild(root, "Child 1")
CALL addChild(root, "Child 2")

// Adding a grandchild to Child 1
DECLARE child1 : TreeNode
SET child1 = root.children[0]
CALL addChild(child1, "Grandchild 1.1")

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

def createTreeNode(val):
    return TreeNode(val)

def addChild(parent, childValue):
    childNode = createTreeNode(childValue)
    parent.children.append(childNode)

# Example usage
root = createTreeNode("Root")

addChild(root, "Child 1")
addChild(root, "Child 2")

# Adding a grandchild to "Child 1"
child1 = root.children[0]
addChild(child1, "Grandchild 1.1")

import java.util.ArrayList;

class TreeNode {
    String value;
    ArrayList<TreeNode> children;

    // Constructor
    public TreeNode(String value) {
        this.value = value;
        this.children = new ArrayList<>();
    }
}

public class TreeExample {

    // Function to create a tree node
    public static TreeNode createTreeNode(String val) {
        return new TreeNode(val);
    }

    // Function to add a child to a parent node
    public static void addChild(TreeNode parent, String childValue) {
        TreeNode childNode = createTreeNode(childValue);
        parent.children.add(childNode);
    }

    public static void main(String[] args) {
        // Create the root node
        TreeNode root = createTreeNode("Root");

        // Add children to the root
        addChild(root, "Child 1");
        addChild(root, "Child 2");

        // Add a grandchild to "Child 1"
        TreeNode child1 = root.children.get(0);
        addChild(child1, "Grandchild 1.1");
    }
}

PROCEDURE traverseTree(node : TreeNode)
    IF node = NULL THEN
        RETURN
    ENDIF

    OUTPUT node.value

    FOR EACH child IN node.children DO
        CALL traverseTree(child)
    NEXT
ENDPROCEDURE

// Call the traversal on the root
CALL traverseTree(root)

def traverseTree(node):
    if node is None:
        return

    print(node.value)

    for child in node.children:
        traverseTree(child)

# Call the traversal
traverseTree(root)

public static void traverseTree(TreeNode node) {
    if (node == null) {
        return;
    }

    System.out.println(node.value);

    for (TreeNode child : node.children) {
        traverseTree(child);
    }
}

// In main:
traverseTree(root);

PROCEDURE addChild(parent : TreeNode, childValue : STRING)
    DECLARE childNode : TreeNode
    SET childNode = createTreeNode(childValue)
    APPEND childNode TO parent.children
ENDPROCEDURE

// Usage:
CALL addChild(root, "New Child")

def addChild(parent, childValue):
    childNode = TreeNode(childValue)
    parent.children.append(childNode)

# Usage:
addChild(root, "New Child")

public static void addChild(TreeNode parent, String childValue) {
    TreeNode childNode = new TreeNode(childValue);
    parent.children.add(childNode);
}

// Usage in main:
addChild(root, "New Child");

PROCEDURE removeChild(parent : TreeNode, targetValue : STRING)
    FOR index FROM 0 TO LENGTH(parent.children) - 1
        IF parent.children[index].value = targetValue THEN
            REMOVE parent.children[index]
            RETURN
        ENDIF
    NEXT
ENDPROCEDURE

// Usage
CALL removeChild(root, "Child 1")

def removeChild(parent, targetValue):
    for i in range(len(parent.children)):
        if parent.children[i].value == targetValue:
            del parent.children[i]
            return  # Exit after removing first match

# Usage:
removeChild(root, "Child 1")

public static void removeChild(TreeNode parent, String targetValue) {
    for (int i = 0; i < parent.children.size(); i++) {
        if (parent.children.get(i).value.equals(targetValue)) {
            parent.children.remove(i);
            return; // Exit after first match
        }
    }
}

// Usage in main:
removeChild(root, "Child 1");