Find the next node in the binary tree

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.