// cs/q/trees/iterate/post_order_test.gpt.cc
// Leetcode 145: Binary Tree Postorder Traversal
// Each test includes an ASCII sketch of the tree and the
// expected post-order traversal.

#include <vector>

#include "cs/q/trees/iterate.hh"
#include "gmock/gmock.h"
#include "gtest/gtest.h"

namespace cs::q::trees {
namespace {

template <typename T, typename L = std::nullptr_t,
          typename R = std::nullptr_t>
Node<T>* NodeOf(T v, L l = nullptr, R r = nullptr) {
  return new Node<T>(v, static_cast<Node<T>*>(l),
                     static_cast<Node<T>*>(r));
}

template <typename T>
void DeleteTree(Node<T>* root) {
  if (root == nullptr) return;
  DeleteTree(root->left);
  DeleteTree(root->right);
  delete root;
}

template <typename T>
std::vector<T> Collect(Node<T>* root) {
  std::vector<T> out;
  PostOrderTreeIterator<T> it(root);
  while (it.HasNext()) {
    out.push_back(it.Next());
  }
  return out;
}

//        (empty)
// expected: {}
TEST(PostOrderTreeIteratorGPT, EmptyTree) {
  Node<int>* root = nullptr;
  EXPECT_THAT(Collect(root), ::testing::ElementsAre());
}

//      1
// expected: 1
TEST(PostOrderTreeIteratorGPT, SingleNode) {
  Node<int>* root = NodeOf(1);
  EXPECT_THAT(Collect(root), ::testing::ElementsAre(1));
  DeleteTree(root);
}

//       3
//      /
//     2
//    /
//   1
// expected: 1 2 3
TEST(PostOrderTreeIteratorGPT, LeftSkewed) {
  Node<int>* root = NodeOf(3, NodeOf(2, NodeOf(1)));
  EXPECT_THAT(Collect(root),
              ::testing::ElementsAre(1, 2, 3));
  DeleteTree(root);
}

//   1
//    \
//     2
//      \
//       3
// expected: 3 2 1
TEST(PostOrderTreeIteratorGPT, RightSkewed) {
  Node<int>* root =
      NodeOf(1, nullptr, NodeOf(2, nullptr, NodeOf(3)));
  EXPECT_THAT(Collect(root),
              ::testing::ElementsAre(3, 2, 1));
  DeleteTree(root);
}

//       4
//     /   \
//    2     6
//   / \   / \
//  1   3 5   7
// expected: 1 3 2 5 7 6 4
TEST(PostOrderTreeIteratorGPT, PerfectBST) {
  Node<int>* root =
      NodeOf(4, NodeOf(2, NodeOf(1), NodeOf(3)),
             NodeOf(6, NodeOf(5), NodeOf(7)));
  EXPECT_THAT(Collect(root),
              ::testing::ElementsAre(1, 3, 2, 5, 7, 6, 4));
  DeleteTree(root);
}

//       5
//     /   \
//    3     8
//   /     /
//  2     7
//   \     \
//    2     9
// expected: 2 2 3 9 7 8 5 (note repeated 2)
TEST(PostOrderTreeIteratorGPT,
     MissingChildrenAndDuplicates) {
  Node<int>* root =
      NodeOf(5, NodeOf(3, NodeOf(2, nullptr, NodeOf(2))),
             NodeOf(8, NodeOf(7, nullptr, NodeOf(9))));
  EXPECT_THAT(Collect(root),
              ::testing::ElementsAre(2, 2, 3, 9, 7, 8, 5));
  DeleteTree(root);
}

//       10
//      /  \
//     5    15
//      \     \
//       6     20
//            /
//           18
// expected: 6 5 18 20 15 10
TEST(PostOrderTreeIteratorGPT, UnbalancedMixed) {
  Node<int>* root = NodeOf(
      10, NodeOf(5, nullptr, NodeOf(6)),
      NodeOf(15, nullptr, NodeOf(20, NodeOf(18), nullptr)));
  EXPECT_THAT(Collect(root),
              ::testing::ElementsAre(6, 5, 18, 20, 15, 10));
  DeleteTree(root);
}

//       4
//     /   \
//    2     5
//   / \
//  1   3
// expected: HasNext toggles false after final Next
TEST(PostOrderTreeIteratorGPT, HasNextDrains) {
  Node<int>* root =
      NodeOf(4, NodeOf(2, NodeOf(1), NodeOf(3)), NodeOf(5));
  PostOrderTreeIterator<int> it(root);
  EXPECT_TRUE(it.HasNext());
  EXPECT_EQ(it.Next(), 1);
  EXPECT_TRUE(it.HasNext());
  EXPECT_EQ(it.Next(), 3);
  EXPECT_TRUE(it.HasNext());
  EXPECT_EQ(it.Next(), 2);
  EXPECT_TRUE(it.HasNext());
  EXPECT_EQ(it.Next(), 5);
  EXPECT_TRUE(it.HasNext());
  EXPECT_EQ(it.Next(), 4);
  EXPECT_FALSE(it.HasNext());
  DeleteTree(root);
}

}  // namespace
}  // namespace cs::q::trees