1448. Count good nodes

1448_solution1_recursive.c

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

static void dfs(struct TreeNode *root, int max, int *count) {
  if (!root)
    return;
  if (root->val >= max) {
    (*count)++;
    max = root->val;
  }
  dfs(root->left, max, count);
  dfs(root->right, max, count);
}

int goodNodes(struct TreeNode *root) {
  int count = 0;
  dfs(root, INT_MIN, &count);
  return count;
}

1448_solution2_iterative.c

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

#define MAX_NODES 100000 // constraint: number of nodes is in [1, 10^5]

struct Frame {
  struct TreeNode *node;
  int maxSoFar;
};

int goodNodes(struct TreeNode *root) {
  static struct Frame stack[MAX_NODES];
  int top = 0, count = 0;
  stack[top++] = (struct Frame){root, INT_MIN};

  while (top > 0) {
    struct Frame f = stack[--top];
    if (!f.node)
      continue;

    if (f.node->val >= f.maxSoFar) {
      count++;
      f.maxSoFar = f.node->val;
    }

    // each node pushes at most two children, so the stack stays within bounds
    if (f.node->right)
      stack[top++] = (struct Frame){f.node->right, f.maxSoFar};
    if (f.node->left)
      stack[top++] = (struct Frame){f.node->left, f.maxSoFar};
  }
  return count;
}

tree_node.h

#pragma once

#include <stddef.h>

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

1448_solution1_recursive.cpp

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

class Solution {
public:
  int goodNodes(TreeNode *root) {
    int count = 0;
    dfs(root, INT_MIN, count);
    return count;
  }

  void dfs(TreeNode *root, int max, int &count) {
    if (!root)
      return;
    if (root->val >= max) {
      count++;
      max = root->val;
    }
    dfs(root->left, max, count);
    dfs(root->right, max, count);
  }
};

1448_solution2_iterative.cpp

#include "tree_node.h"
#include <climits>
#include <stack>
#include <utility>

using namespace std;

int goodNodes(TreeNode *root) {
  int count = 0;
  stack<pair<TreeNode *, int>> st;
  st.push({root, INT_MIN});

  while (!st.empty()) {
    auto [node, maxSoFar] = st.top();
    st.pop();

    if (!node)
      continue;

    if (node->val >= maxSoFar) {
      count++;
      maxSoFar = node->val;
    }

    st.push({node->left, maxSoFar});
    st.push({node->right, maxSoFar});
  }
  return count;
}

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

1448_solution1_recursive.go

package trees

import "math"

func goodNodes(root *TreeNode) int {
    count := 0

    var dfs func(node *TreeNode, maxSoFar int)
    dfs = func(node *TreeNode, maxSoFar int) {
        if node == nil {
            return
        }
        if node.Val >= maxSoFar {
            count++
            maxSoFar = node.Val
        }
        dfs(node.Left, maxSoFar)
        dfs(node.Right, maxSoFar)
    }

    dfs(root, math.MinInt)
    return count
}

1448_solution2_iterative.go

package trees

import "math"

type frame struct {
    node     *TreeNode
    maxSoFar int
}

func goodNodes(root *TreeNode) int {
    count := 0
    stack := []frame{{root, math.MinInt}}

    for len(stack) > 0 {
        f := stack[len(stack)-1]
        stack = stack[:len(stack)-1]

        if f.node == nil {
            continue
        }

        if f.node.Val >= f.maxSoFar {
            count++
            f.maxSoFar = f.node.Val
        }

        stack = append(stack, frame{f.node.Left, f.maxSoFar}, frame{f.node.Right, f.maxSoFar})
    }
    return count
}

tree_node.go

package trees

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

1448_solution1_recursive.java

class Solution {
    private int count;

    public int goodNodes(TreeNode root) {
        count = 0;
        dfs(root, Integer.MIN_VALUE);
        return count;
    }

    private void dfs(TreeNode node, int maxSoFar) {
        if (node == null)
            return;
        if (node.val >= maxSoFar) {
            count++;
            maxSoFar = node.val;
        }
        dfs(node.left, maxSoFar);
        dfs(node.right, maxSoFar);
    }
}

1448_solution2_iterative.java

import java.util.ArrayDeque;
import java.util.Deque;

class Solution {
    public int goodNodes(TreeNode root) {
        int count = 0;
        Deque<TreeNode> nodes = new ArrayDeque<>();
        Deque<Integer> maxes = new ArrayDeque<>();
        nodes.push(root);
        maxes.push(Integer.MIN_VALUE);

        while (!nodes.isEmpty()) {
            TreeNode node = nodes.pop();
            int maxSoFar = maxes.pop();

            if (node.val >= maxSoFar) {
                count++;
                maxSoFar = node.val;
            }

            if (node.left != null) {
                nodes.push(node.left);
                maxes.push(maxSoFar);
            }
            if (node.right != null) {
                nodes.push(node.right);
                maxes.push(maxSoFar);
            }
        }
        return count;
    }
}

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

1448_solution1_recursive.js

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

var goodNodes = function (root) {
  let count = 0;

  const dfs = (node, maxSoFar) => {
    if (!node) return;
    if (node.val >= maxSoFar) {
      count++;
      maxSoFar = node.val;
    }
    dfs(node.left, maxSoFar);
    dfs(node.right, maxSoFar);
  };

  dfs(root, -Infinity);
  return count;
};

1448_solution2_iterative.js

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

var goodNodes = function (root) {
  let count = 0;
  const stack = [[root, -Infinity]];

  while (stack.length > 0) {
    let [node, maxSoFar] = stack.pop();
    if (!node) continue;

    if (node.val >= maxSoFar) {
      count++;
      maxSoFar = node.val;
    }

    stack.push([node.left, maxSoFar], [node.right, maxSoFar]);
  }
  return count;
};

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;

1448_solution1_recursive.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def goodNodes(self, root: Optional[TreeNode]) -> int:
        count = 0

        def dfs(node: Optional[TreeNode], max_so_far: int) -> None:
            nonlocal count
            if not node:
                return
            if node.val >= max_so_far:
                count += 1
                max_so_far = node.val
            dfs(node.left, max_so_far)
            dfs(node.right, max_so_far)

        dfs(root, float("-inf"))
        return count

1448_solution2_iterative.py

from typing import Optional

from tree_node import TreeNode


class Solution:
    def goodNodes(self, root: Optional[TreeNode]) -> int:
        count = 0
        stack = [(root, float("-inf"))]

        while stack:
            node, max_so_far = stack.pop()
            if not node:
                continue

            if node.val >= max_so_far:
                count += 1
                max_so_far = node.val

            stack.append((node.left, max_so_far))
            stack.append((node.right, max_so_far))
        return count

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

1448_solution1_recursive.rs

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

use crate::tree_node::TreeNode;

type Link = Option<Rc<RefCell<TreeNode>>>;

impl Solution {
    pub fn good_nodes(root: Link) -> i32 {
        let mut count = 0;
        Self::dfs(&root, i32::MIN, &mut count);
        count
    }

    fn dfs(node: &Link, max_so_far: i32, count: &mut i32) {
        if let Some(n) = node {
            let n = n.borrow();

            let mut max_so_far = max_so_far;
            if n.val >= max_so_far {
                *count += 1;
                max_so_far = n.val;
            }
            Self::dfs(&n.left, max_so_far, count);
            Self::dfs(&n.right, max_so_far, count);
        }
    }
}

1448_solution2_iterative.rs

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

use crate::tree_node::TreeNode;

impl Solution {
    pub fn good_nodes(root: Option<Rc<RefCell<TreeNode>>>) -> i32 {
        let mut count = 0;
        let mut stack = vec![(root, i32::MIN)];

        while let Some((node, max_so_far)) = stack.pop() {
            let Some(node) = node else { continue };
            let node = node.borrow();

            let mut max_so_far = max_so_far;
            if node.val >= max_so_far {
                count += 1;
                max_so_far = node.val;
            }

            stack.push((node.left.clone(), max_so_far));
            stack.push((node.right.clone(), max_so_far));
        }
        count
    }
}

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,
        }
    }
}