Explanation of class Definition for Binary Trees in leetcode

Question

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

Samwise Ganges · Accepted Answer · 2024-10-16 06:17:31Z

2

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);

edited Oct 16, 2024 at 6:17

Samwise Ganges

5827 silver badges11 bronze badges

answered Feb 16, 2023 at 14:21

trincot

357k38 gold badges282 silver badges338 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Juan Marino Over a year ago

great explanation!! Thank you so much, this makes more sense now

Egret Over a year ago

well explained. Is there also a python version of this?

trincot Over a year ago

@Egret, looking for this?

Pointy · Accepted Answer · 2023-02-16 14:47:34Z

-1

That array representation is usually called a "heap". The positions in the array represent nodes in the tree based on the index. A node at position n has children at positions 2n+1 and 2n+2. The node at position zero is the root.

The root's children are at 2x0+1 and 2x0+2, positions 1 and 2 in the array. The left child of the root at position 1 is 9, and it's children are at positions 3 and 4, the two null values.

edit — apparently the LeetCode representation isn't always a heap, but heaps are a useful tree representation nevertheless so I'll leave this be.

edited Feb 16, 2023 at 14:47

answered Feb 16, 2023 at 14:29

Pointy

415k62 gold badges600 silver badges631 bronze badges

3 Comments

trincot Over a year ago

The LeetCode input format is not generally a heap. It happens to be so for the example, but when the tree is more unbalanced, the "slots" whose parents are denoted with null are not represented anymore in the array notation, so the representation is somewhat shorter, and you cannot rely on the formula 2 * n + 1.

Pointy Over a year ago

@trincot OK that's interesting, I confess to knowing literally nothing (well except for that, now) about "leetcode"

Juan Marino Over a year ago

even though heaps wasn't completly true as an answer, I learned something from this comment. Thank you both!!

Collectives™ on Stack Overflow

Explanation of class Definition for Binary Trees in leetcode

2 Answers 2

3 Comments

3 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related