Next Node in a Binary Tree

1. Problem Description

Given a binary tree and one of its nodes, find and return the next node in inorder traversal order. Note that each tree node contains not only left and right child pointers, but also a pointer to its parent.

2. Approach

• Find the root, then perform inorder traversal
• Successor node in tree

3. Implementation

3.1. Find the Root, Then Inorder Traversal

type TreeLinkNode struct {
	Val   int
	Left  *TreeLinkNode
	Right *TreeLinkNode
	Next  *TreeLinkNode
}

// Time complexity: O(N)
// Space complexity: O(N)
func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}

	root := pNode
	for root.Next != nil {
		root = root.Next
	}

	linkNodes := make([]*TreeLinkNode, 0)
	inOrder(root, &linkNodes)
	for i := 0; i < len(linkNodes); i++ {
		if linkNodes[i] == pNode {
			if i+1 < len(linkNodes) {
				return linkNodes[i+1]
			}
		}
	}

	return nil
}

3.2. Successor Node

• go

func GetNext(pNode *TreeLinkNode) *TreeLinkNode {
	if pNode == nil {
		return nil
	}
    // If there is a right subtree, find its leftmost node
	current := pNode.Right
	if current != nil {
		for current.Left != nil {
			current = current.Left
		}
		return current
	}

    // If there is a parent node, move upward to find the first node whose left child is the current node
	current = pNode
	for current.Next != nil  {
        if current.Next.Left == current {
            return current.Next
        }
        current = current.Next
	}

	return nil
}

4. References

• Next Node in a Binary Tree - NowCoder
• Interview Question 04.06. Successor - LeetCode