Binary Search Tree "stack" explanation

Question

I have a very simple implemention of BST in C#. The code:

class Node
{
    public int? value;
    public Node parent;
    public Node left;
    public Node right;

    public Node(int? value, Node parent = null)
    {
        this.value = value;
        this.parent = parent;
    }
}

class BST
{
    public Node root;
    public List<Node> tree = new List<Node>();

    public BST(int? value = null)
    {
        if (value != null)
        {
            this.root = new Node(value);
            this.tree.Add(this.root);
        }
    }

    public Node insert(int value)
    {
        Node node = this.root;

        if (node == null)
        {
            this.root = new Node(value);
            this.tree.Add(this.root);

            return this.root;
        }

        while (true)
        {
            if (value > node.value)
            {
                if (node.right != null)
                {
                    node = node.right;
                }
                else
                {
                    node.right = new Node(value, node);
                    node = node.right;
                    break;
                }
            }
            else if (value < node.value)
            {
                if (node.left != null)
                {
                    node = node.left;
                }
                else
                {
                    node.left = new Node(value, node);
                    node = node.left;
                    break;
                }
            }
            else
            {
                break;
            }
        }
        return node;
    }
}

class Program
{
    static void Main()
    {
        BST superTree = new BST(15);
        superTree.insert(14);
        superTree.insert(25);
        superTree.insert(2);
    }
}

My Question is regarding the "Insert" method of the BST class.

How exactly its "return" work when I just call it in the main method? How does it know to put that "node" on the "left"? I am not referencing "root.left" anywhere but somehow it gets properly inserted.

I realized at some point that some kind of recursion occurs there, but its been like 6 hours and I still can't understand how this method properly works.

I appreaciate any explanation of that "insert" method.Thanks.

Answer 1

Node node = this.root;

Your code always starts with the root, because of this line. It's only after node is no longer null that node be re-assigned to something other than root. The rest of the code works on node.left, but because your code begins with root as above, node.left is actually referencing root at the start.