preface

Given a binary tree containing a parent node reference and one of its nodes, how do I find the next node in the sequential traversal sequence of this node?

This article will share the solution and implementation code for this problem, and welcome interested developers to read this article.

Problem analysis

As stated in the introduction, we know as follows:

  • A binary tree containing references to the parent node
  • The node to look for

Problems we need to solve:

  • Find the next node in the sequential traversal sequence of nodes to be searched

Next, we derive the rule of the next node through examples. Let’s draw a binary search tree, as shown below:

            8
           / \
          6   13/ \ \3  7 9  15
Copy the code
  • For example, if we look for the next node of 6, we know that its next node is 7 according to the rules of middle order traversal
  • The next node of 8 is 9
  • The next node of 3 is 6
  • The next node of 7 is 8

From the above examples, we can analyze the following information:

  • The node to be searched has a right subtree, so its next node is the leftmost child in the right subtree
  • The node to be found does not contain the right subtree:
    • The current node is the left child of the parent node, so its next node is the parent node itself
    • The current node belongs to the right child of the parent node, so you need to traverse the pointer to the parent node until you find a node that is the left child of its parent node

So this might be a little convoluted, but if you plug it into the problem a couple of times, you’ll get the idea.

Implementation approach

  • A reference to its parent is saved when a node is inserted into a binary tree
  • Call the binary tree search node method to find the node information to look for
  • Check whether the found node has a right subtree
  • If it exists, it traverses its left subtree to the leaf node and returns it.
  • If not, it traverses its parent node to the root node until it finds a node that is equal to the left child of its parent node and returns it.

The implementation code

Next, let’s translate this idea into code that uses binary trees in my other article: TypeScript implementing binary search trees

Search for the node to find

We need to find the node information of the node to be searched in the binary tree to continue the following steps. The code for searching the node is as follows:

import { Node } from "./Node.ts";

export default class BinarySearchTree<T> {
    protected root: Node<T> | undefined;

    constructor(protected compareFn: ICompareFunction<T> = defaultCompare) {
        this.root = undefined;
    }
  
    // Search for a specific value
    search(key: T): boolean | Node<T> {
        return this.searchNode(<Node<T>>this.root, key);
    }

    // Search for nodes
    private searchNode(node: Node<T>, key: T): boolean | Node<T> {
        if (node == null) {
            return false;
        }

        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            // The key to look for is on the left of the node
            return this.searchNode(<Node<T>>node.left, key);
        } else if (this.compareFn(key, node.key) === Compare.BIGGER_THAN) {
            // The key is on the right side of the node
            return this.searchNode(<Node<T>>node.right, key);
        } else {
            // The node has been found
            returnnode; }}}Copy the code

Save the parent node reference

The binary tree here is slightly different from the binary tree we implemented. The reference of the parent node needs to be saved when the node is inserted. The implementation code is as follows:

export default class BinarySearchTree<T> {
    // Insert method
    insert(key: T): void {
        if (this.root == null) {
            // If the root node does not exist, create a new node
            this.root = new Node(key);
        } else {
            // Insert child nodes in the root node
            this.insertNode(this.root, key); }}// Node is inserted
    protected insertNode(node: Node<T>, key: T): void {
        // If the key of the new node is smaller than the key of the current node, the new node is inserted to the left of the current node
        // If the key of the new node is greater than the key of the current node, insert the new node to the right of the current node
        if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
            if (node.left == null) {
                // The left subtree of the current node is null and inserted directly
                node.left = new Node(key, node);
            } else {
                // Recurse down from the current node (left subtree) to find the null position and insert it
                this.insertNode(node.left, key); }}else {
            if (node.right == null) {
                // The right subtree of the current node is null and inserted directly
                node.right = new Node(key, node);
            } else {
                // Recurse down from the current node (right subtree) to find the null position and insert it
                this.insertNode(node.right, key); }}}}/** * Binary tree helper class: used to store each node of the binary tree */
export class Node<K> {
    public left: Node<K> | undefined;
    public right: Node<K> | undefined;
    public parent: Node<K> | undefined;
    constructor(publickey: K, parent? : Node<K>) {
        this.left = undefined;
        this.right = undefined;
        console.log(key, "Parent node", parent? .key);this.parent = parent;
    }

    toString(): string {
        return `The ${this.key}`; }}Copy the code

Let’s test the above code to verify that the parent node reference succeeds:

const tree = new BinarySearchTree();
tree.insert(8);
tree.insert(6);
tree.insert(3);
tree.insert(7);
tree.insert(13);
tree.insert(9);
tree.insert(15);
Copy the code

After a long time trying to save the parent reference, I finally asked my friend _Dreams๐Ÿ˜ for help.

Find the next node

Next, we can implement this algorithm according to the law of nodes, the implementation code is as follows:

export class TreeOperate<T> {
    /** * Find the next node of the binary tree * rule: * 1. Enter a binary tree containing a reference to the parent node and one of its nodes * 2. Find the next node in the sequential traversal sequence * * for example: * 8 * / \ * 6 13 * / \ / * 3 7 9 15 * * 6 the next node is 7, 8 the next node is 9 * * If a node has a right subtree, its next node is the leftmost child in the right subtree * 2. If a node has no right subtree: * (1). The current node belongs to the left child of the parent node, then its next node is the parent node itself * (2). The current node belongs to the right child of the parent node. Follow the pointer to the parent node until you find a node * */ that is the left child of its parent node
    findBinaryTreeNextNode(tree: BinarySearchTree<number>, node: number) :null | Node<number> {
        // Search for nodes
        const result: Node<number> | boolean = tree.search(node);
        if (result == null) throw "Node does not exist";
        let currentNode = result as Node<number>;
        // The right subtree exists
        if (currentNode.right) {
            currentNode = currentNode.right;
            // Take the leftmost child of the right subtree
            while (currentNode.left) {
                currentNode = currentNode.left;
            }
            return currentNode;
        }

        // The right subtree does not exist
        while (currentNode.parent) {
            The condition is true if the current node is equal to the left child of its parent
            if (currentNode === currentNode.parent.left) {
                return currentNode.parent;
            }
            // If the condition is not true, continue to obtain its parent node
            currentNode = currentNode.parent;
        }
        return null; }}Copy the code

Let’s test the above code with an example:

// Build a binary search tree
const tree = new BinarySearchTree();
tree.insert(8);
tree.insert(6);
tree.insert(3);
tree.insert(7);
tree.insert(13);
tree.insert(9);
tree.insert(15);
// Find the next node
const nextNode = treeOperate.findBinaryTreeNextNode(tree, 7);
console.log("The next node of seven.", nextNode.toString());

Copy the code

The code address

The complete code is as follows:

  • TreeOperate.ts

  • BinarySearchTree.ts

Write in the last

  • If there are any errors in this article, please correct them in the comments section. If this article helped you, please like it and follow ๐Ÿ˜Š
  • This article was first published in nuggets. Reprint is prohibited without permission ๐Ÿ’Œ