Tree: Height of a Binary Tree

  • + 1 comment

    C++ using a stack and iteration instead of recursion.

        int height(Node* root) {
            struct Frame {
                Node* node{};
                int height = 0;
            };
            std::stack<Frame> stack;
            stack.push({root});
            int max = INT_MIN;
            while (!stack.empty()) {
                const auto top = stack.top();
                stack.pop();
                max = std::max(max, top.height);
                if (top.node->right)
                    stack.push({top.node->right, top.height + 1});
                if (top.node->left)
                    stack.push({top.node->left, top.height + 1});
            }
            return max;
        }
    
    • + 0 comments

      C++, recursion.

          int height(Node* root) {
              if (!root || (!root->left && !root->right))
                  return 0;
              return 1 + std::max(
                  height(root->left),
                  height(root->right)
              );
          }