104. Max tree depth

104_solution1_recursion.c

#include "tree_node.h"

static int find_depth(struct TreeNode *root, int count) {
  if (!root)
    return count;

  int l = find_depth(root->left, count + 1);
  int r = find_depth(root->right, count + 1);
  return l > r ? l : r;
}

int maxDepth(struct TreeNode *root) { return find_depth(root, 0); }

104_solution2_iterative.c

#include "tree_node.h"

#define MAX_NODES 10000 // constraint: number of nodes is in [0, 10^4]

int maxDepth(struct TreeNode *root) {
  static struct TreeNode *queue[MAX_NODES];
  int head = 0, tail = 0;
  if (root)
    queue[tail++] = root;

  int depth = 0;
  while (head < tail) {
    int size = tail - head;
    depth++;

    for (int i = 0; i < size; i++) {
      struct TreeNode *cur = queue[head++];

      if (cur->left)
        queue[tail++] = cur->left;
      if (cur->right)
        queue[tail++] = cur->right;
    }
  }

  return depth;
}

tree_node.h

#pragma once

#include <stddef.h>

// Definition for a binary tree node.
struct TreeNode {
  int val;
  struct TreeNode *left;
  struct TreeNode *right;
};

104_solution1_recursion.cpp

#include "tree_node.h"
#include <algorithm>

using namespace std;

class Solution {
public:
  int maxDepth(TreeNode *root) { return findDepth(root, 0); }

  int findDepth(TreeNode *root, int count) {
    if (!root)
      return count;
    return max(findDepth(root->left, count + 1),
               findDepth(root->right, count + 1));
  }
};

104_solution2_iterative.cpp

#include "tree_node.h"
#include <queue>

using namespace std;

class Solution {
public:
  int maxDepth(TreeNode *root) {
    queue<TreeNode *> q;
    if (root)
      q.push(root);

    int depth = 0;
    while (!q.empty()) {
      int size = q.size();
      depth++;

      for (int i = 0; i < size; i++) {
        TreeNode *cur = q.front();
        q.pop();

        if (cur->left)
          q.push(cur->left);
        if (cur->right)
          q.push(cur->right);
      }
    }

    return depth;
  }
};

tree_node.h

#pragma once

// Definition for a binary tree node.
struct TreeNode {
  int val;
  TreeNode *left;
  TreeNode *right;
  TreeNode() : val(0), left(nullptr), right(nullptr) {}
  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  TreeNode(int x, TreeNode *left, TreeNode *right)
      : val(x), left(left), right(right) {}
};

104_solution1_recursion.go

package trees

func maxDepth(root *TreeNode) int {
    return findDepth(root, 0)
}

func findDepth(root *TreeNode, count int) int {
    if root == nil {
        return count
    }
    return max(findDepth(root.Left, count+1), findDepth(root.Right, count+1))
}

104_solution2_iterative.go

package trees

func maxDepth(root *TreeNode) int {
    queue := []*TreeNode{}
    if root != nil {
        queue = append(queue, root)
    }

    depth := 0
    for len(queue) > 0 {
        size := len(queue)
        depth++

        for i := 0; i < size; i++ {
            cur := queue[i]

            if cur.Left != nil {
                queue = append(queue, cur.Left)
            }
            if cur.Right != nil {
                queue = append(queue, cur.Right)
            }
        }
        queue = queue[size:]
    }

    return depth
}

tree_node.go

package trees

// Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

104_solution1_recursion.java

class Solution {
    public int maxDepth(TreeNode root) {
        return findDepth(root, 0);
    }

    private int findDepth(TreeNode root, int count) {
        if (root == null)
            return count;
        return Math.max(findDepth(root.left, count + 1), findDepth(root.right, count + 1));
    }
}

104_solution2_iterative.java

import java.util.ArrayDeque;
import java.util.Queue;

class Solution {
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> q = new ArrayDeque<>();
        if (root != null)
            q.add(root);

        int depth = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            depth++;

            for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();

                if (cur.left != null)
                    q.add(cur.left);
                if (cur.right != null)
                    q.add(cur.right);
            }
        }

        return depth;
    }
}

TreeNode.java

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

104_solution1_recursion.js

const TreeNode = require("./tree_node");

var maxDepth = function (root) {
  const findDepth = (node, count) => {
    if (!node) return count;
    return Math.max(findDepth(node.left, count + 1), findDepth(node.right, count + 1));
  };

  return findDepth(root, 0);
};

104_solution2_iterative.js

const TreeNode = require("./tree_node");

var maxDepth = function (root) {
  let level = root ? [root] : [];

  let depth = 0;
  while (level.length > 0) {
    depth++;

    // the next level is every child of the current one
    const next = [];
    for (const cur of level) {
      if (cur.left) next.push(cur.left);
      if (cur.right) next.push(cur.right);
    }
    level = next;
  }

  return depth;
};

tree_node.js

// 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;
}

module.exports = TreeNode;

104_solution1_recursion.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        return self.findDepth(root, 0)

    def findDepth(self, root: Optional[TreeNode], count: int) -> int:
        if not root:
            return count
        return max(
            self.findDepth(root.left, count + 1),
            self.findDepth(root.right, count + 1),
        )

104_solution2_iterative.py

from collections import deque
from typing import Optional

from tree_node import TreeNode


class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        q = deque([root] if root else [])

        depth = 0
        while q:
            depth += 1

            for _ in range(len(q)):
                cur = q.popleft()

                if cur.left:
                    q.append(cur.left)
                if cur.right:
                    q.append(cur.right)

        return depth

tree_node.py

# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

104_solution1_recursion.rs

use std::cell::RefCell;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        Self::find_depth(&root, 0)
    }

    fn find_depth(root: &Option<Rc<RefCell<TreeNode>>>, count: i32) -> i32 {
        match root {
            None => count,
            Some(node) => {
                let n = node.borrow();
                Self::find_depth(&n.left, count + 1).max(Self::find_depth(&n.right, count + 1))
            }
        }
    }
}

104_solution2_iterative.rs

use std::cell::RefCell;
use std::collections::VecDeque;
use std::rc::Rc;

use crate::tree_node::TreeNode;

impl Solution {
    pub fn max_depth(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut q = VecDeque::new();
        if let Some(r) = root {
            q.push_back(r);
        }

        let mut depth = 0;
        while !q.is_empty() {
            depth += 1;

            for _ in 0..q.len() {
                let cur = q.pop_front().unwrap();
                let n = cur.borrow();

                if let Some(l) = &n.left {
                    q.push_back(Rc::clone(l));
                }
                if let Some(r) = &n.right {
                    q.push_back(Rc::clone(r));
                }
            }
        }

        depth
    }
}

tree_node.rs

use std::cell::RefCell;
use std::rc::Rc;

// Definition for a binary tree node.
#[derive(Debug, PartialEq, Eq)]
pub struct TreeNode {
    pub val: i32,
    pub left: Option<Rc<RefCell<TreeNode>>>,
    pub right: Option<Rc<RefCell<TreeNode>>>,
}

impl TreeNode {
    #[inline]
    pub fn new(val: i32) -> Self {
        TreeNode {
            val,
            left: None,
            right: None,
        }
    }
}