C# Coding Test Course, Understanding Trees

1. Problem Description

Trees are widely used as a data structure where insertion and deletion occur frequently.
In this article, we will explain the basic concepts of binary trees and their applications, and solve related algorithm problems together.

Problem: Find the Maximum Depth of a Binary Tree

Write a function to determine the maximum depth of a binary tree given the root node of the tree.

Problem Requirements

  • Each node of the tree has an integer value and can have left and right children.
  • A leaf node refers to a node with no children.
  • The maximum depth of the tree refers to the length from the root node to a leaf node.

2. Example

    Input:     3
             / \
            9   20
               /  \
              15   7
    Output: 3

Explanation: The maximum depth of the binary tree is 3 (from root node 3 to node 20 to node 15 or 7).

3. Understanding Tree Structures

A binary tree is a tree where each node can have at most two children.
Binary trees can be represented in various ways, but it is common to implement nodes as classes or structures.
Below is an example of a binary tree implemented in C#:

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

4. Algorithm to Find Maximum Depth

The maximum depth can be calculated using recursion.
For each node, follow these steps:

  1. If the current node is null, the depth is 0.
  2. Recursively calculate the depth of the current node’s left and right children.
  3. Return the current node’s depth by adding 1 to the larger of the left and right child depths.

5. C# Code Implementation

    public int MaxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        
        int leftDepth = MaxDepth(root.left);
        int rightDepth = MaxDepth(root.right);
        
        return Math.Max(leftDepth, rightDepth) + 1;
    }

6. Complete Code

    public class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int x) {
            val = x;
            left = null;
            right = null;
        }
    }

    public class Solution {
        public int MaxDepth(TreeNode root) {
            if (root == null) {
                return 0;
            }
            
            int leftDepth = MaxDepth(root.left);
            int rightDepth = MaxDepth(root.right);
            
            return Math.Max(leftDepth, rightDepth) + 1;
        }
    }

7. Code Analysis

Key points to note in the above code:

  • The tree is traversed through recursive calls, calculating the depth of each node.
  • The Math.Max function is used to calculate the maximum of the two depths.
  • The base case (when the root is null) is handled properly to prevent infinite loops.

8. Time Complexity

The time complexity of this algorithm is O(N).
Here, N is the number of nodes, as every node needs to be visited once.

9. Additional Information: Tree Traversal Methods

When dealing with trees, there are various traversal methods. The most common are:

  • Pre-order: Current node → Left child → Right child
  • In-order: Left child → Current node → Right child
  • Post-order: Left child → Right child → Current node

Specific problems can also be solved using these traversal methods. The details on this will be covered in future blog posts.

10. Conclusion

This post focused on the problem of finding the maximum depth of a binary tree.
Understanding tree structures is important as they are powerful tools for solving various problems, so it’s essential to grasp the theory and practice related problems frequently.
In the next session, we will explore other tree-related problems and their solutions.