\n 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.\n<\/p>\n
\n 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:\n<\/p>\n
\n Let’s solve the following problem. Write a function that calculates the depth of a given binary tree.\n<\/p>\n
\n 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.\n<\/p>\n
\nInput: \n 3\n \/ \\\n 9 20\n \/ \\\n 15 7\n<\/pre>\nExample Output<\/h3>\n
\nOutput: 3\n<\/pre>\nSolution Approach<\/h3>\n
\n This problem can be solved using Depth First Search (DFS) or Breadth First Search (BFS) methods. Here, we will explain the approach using DFS.\n<\/p>\n
1. Recursive Approach<\/h4>\n
\n We can visit the left and right child nodes recursively at each node to calculate the depth. The basic idea is as follows:\n<\/p>\n
\n
- If the node is
null<\/code>, return 0.<\/li>\n- Calculate the depth of the current node’s left and right children.<\/li>\n
- Return the maximum of the left and right depths plus 1 for the parent node’s depth.<\/li>\n<\/ol>\n
2. Code Implementation<\/h4>\n
\n Below is the code implemented in JavaScript.\n<\/p>\n
\nclass TreeNode {\n constructor(val) {\n this.val = val;\n this.left = null;\n this.right = null;\n }\n}\n\nfunction maxDepth(root) {\n if (root === null) {\n return 0;\n }\n const leftDepth = maxDepth(root.left);\n const rightDepth = maxDepth(root.right);\n return Math.max(leftDepth, rightDepth) + 1;\n}\n<\/code><\/pre>\n3. Code Explanation<\/h3>\n
\n
- TreeNode:<\/strong> This class defines the nodes of a tree. Each node has a value and possesses left and right children.<\/li>\n
- maxDepth:<\/strong> This function recursively calculates the depth. It returns 0 if
root<\/code> isnull<\/code> and otherwise calculates and returns the larger value from the left and right child depths.<\/li>\n<\/ul>\n4. Testing<\/h4>\n
\n Let’s test the `maxDepth` function using the provided example. You can add the following code.\n<\/p>\n
\n\/\/ Create a binary tree\nconst root = new TreeNode(3);\nroot.left = new TreeNode(9);\nroot.right = new TreeNode(20);\nroot.right.left = new TreeNode(15);\nroot.right.right = new TreeNode(7);\n\n\/\/ Calculate depth\nconsole.log(maxDepth(root)); \/\/ Output: 3\n<\/code><\/pre>\nConclusion<\/h2>\n
\n 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.\n<\/p>\n
<\/body><\/p>\n","protected":false},"excerpt":{"rendered":"