JavaScript Coding Test Course, Learn About Trees

A tree is one of the data structures used to store data hierarchically. In this course, we will explore the basic concepts of trees and learn how to solve tree-related algorithm problems using JavaScript.

What is a Tree?

A tree is a non-linear data structure composed of nodes. Each node contains data and connections (edges) to child nodes. It starts from a single root node and can have several child nodes below it, and each child node can also have its own child nodes. The main uses of trees are as follows:

  • Hierarchical data representation (e.g., family trees, organizational charts)
  • Data searching (e.g., binary search trees)
  • Solving various problems (e.g., shortest path problems)

Components of a Tree

  • Root Node: The topmost node of the tree, it is the ancestor of all other nodes.
  • Edge: A line that connects nodes, linking parent nodes to child nodes.
  • Leaf Node: A node that has no child nodes; it is a node that cannot be expanded further.
  • Subtree: A tree consisting of the child nodes of a specific node.

Tree Problem: Calculate the Depth of a Given Binary Tree

Let’s solve the following problem. Write a function that calculates the depth of a given binary tree.

Problem Description

Given a binary tree, write a function that returns the maximum depth of the binary tree. The depth is defined as the distance from the root node to the deepest leaf node.

Example Input

Input: 
       3
      / \
     9  20
        /  \
       15   7

Example Output

Output: 3

Solution Approach

This problem can be solved using Depth First Search (DFS) or Breadth First Search (BFS) methods. Here, we will explain the approach using DFS.

1. Recursive Approach

We can visit the left and right child nodes recursively at each node to calculate the depth. The basic idea is as follows:

  1. If the node is null, return 0.
  2. Calculate the depth of the current node’s left and right children.
  3. Return the maximum of the left and right depths plus 1 for the parent node’s depth.

2. Code Implementation

Below is the code implemented in JavaScript. 


class TreeNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
    }
}

function maxDepth(root) {
    if (root === null) {
        return 0;
    }
    const leftDepth = maxDepth(root.left);
    const rightDepth = maxDepth(root.right);
    return Math.max(leftDepth, rightDepth) + 1;
}

3. Code Explanation

  • TreeNode: This class defines the nodes of a tree. Each node has a value and possesses left and right children.
  • maxDepth: This function recursively calculates the depth. It returns 0 if root is null and otherwise calculates and returns the larger value from the left and right child depths.

4. Testing

Let’s test the `maxDepth` function using the provided example. You can add the following code. 


// Create a binary tree
const root = new TreeNode(3);
root.left = new TreeNode(9);
root.right = new TreeNode(20);
root.right.left = new TreeNode(15);
root.right.right = new TreeNode(7);

// Calculate depth
console.log(maxDepth(root)); // Output: 3

Conclusion

We have explored how to calculate the maximum depth of a tree using JavaScript and the process of solving algorithm problems. Understanding trees will help solve many programming challenges. Practice various tree problems to build a deep understanding of tree structures.