Explanation of class Definition for Binary Trees in leetcode

Was hoping someone could help me understand how this class works. I'm currently taking a javascript algorithms in udemy and the way they explain how to do all operations in a binary tree is a little different than what leetcode shows.

In the course, the tree definition is the same or very similar to leetcode:

class Node {
    constructor(value){
        this.value = value;
        this.left = null;
        this.right = null;
    }
} 

class BinarySearchTree {
    constructor(){
        this.root = null;
    }
}

however, the values are first inserted as nodes before doing any other operation:

insert(value){
        var newNode = new Node(value);
        if(this.root === null){
            this.root = newNode;
            return this;
        }
        var current = this.root;
        while(true){
            if(value === current.value) return undefined;
            if(value < current.value){
                if(current.left === null){
                    current.left = newNode;
                    return this;
                }
                current = current.left;
            } else {
                if(current.right === null){
                    current.right = newNode;
                    return this;
                } 
                current = current.right;
            }
        }
    }

On Leetcode, the values are passed as an array, and thats what throws me off a little:

Definition for a binary tree node.

* function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }

* @param {TreeNode} root
 * @return {number}

Looking at a simple solution for finding the max depth:

var maxDepth = function(root) {
     if(!root) return 0;
    
    return Math.max(maxDepth(root.left) , maxDepth(root.right) ) +1
};

given the array root = [3,9,20,null,null,15,7],

how do we know that root.left is 9 and root.right is 20. Then the next level, root.left.left is null and root.left.right is null. Then root.right.left is 15 and root.right.right is 7.

Just not sure how the array translates into that

Thanks!

tried adding the nodes one by one then perfomring binary tree operations

Solution

On Leetcode, the values are passed as an array

This is a misunderstanding.

Values are not passed as an array. Your function gets an instance of TreeNode as argument (or null). LeetCode let's you specify input in a kind of JSON format, but that is just text that LeetCode will first translate to a TreeNode based tree, before calling your function.

The text input follows a kind of breadth-first (BFS) traversal of the tree it is supposed to represent. So [3,9,20,null,null,15,7] represents this tree:

The two null occurrences indicate that the node with value 9 has no left nor right child.

In case you want to convert an array (based on the input notation) to a tree yourself (the task that LeetCode does for you), you could use a function like this:

function TreeNode(val, left, right) { // LeetCode's code
    this.val = (val===undefined ? 0 : val)
    this.left = (left===undefined ? null : left)
    this.right = (right===undefined ? null : right)
}

function makeTree(arr) {
    if (!arr) return null; // empty tree
    const values = arr[Symbol.iterator]();
    const root = new TreeNode(values.next().value);
    const queue = new Set().add(root);
    for (const node of queue) {
        for (const side of ["left", "right"]) {
             const value = values.next().value;
             if (value != null) queue.add(node[side] = new TreeNode(value));
        }
    }
    return root;
}

// Example use
const arr = [3,9,20,null,null,15,7];
const root = makeTree(arr);
console.log(root);