boundaryTraversal<T> function

List<T> boundaryTraversal<T>(BinaryTreeNode<T>? root)

Implementation

List<T> boundaryTraversal<T>(BinaryTreeNode<T>? root) {
  final List<T> result = [];
  if (root == null) return result;
  bool isLeaf(BinaryTreeNode<T> node) =>
      node.left == null && node.right == null;
  void addLeftBoundary(BinaryTreeNode<T>? node) {
    while (node != null) {
      if (!isLeaf(node)) result.add(node.value);
      node = node.left ?? node.right;
    }
  }

  void addLeaves(BinaryTreeNode<T>? node) {
    if (node == null) return;
    if (isLeaf(node)) {
      result.add(node.value);
      return;
    }
    addLeaves(node.left);
    addLeaves(node.right);
  }

  void addRightBoundary(BinaryTreeNode<T>? node, List<T> stack) {
    while (node != null) {
      if (!isLeaf(node)) stack.add(node.value);
      node = node.right ?? node.left;
    }
  }

  result.add(root.value);
  addLeftBoundary(root.left);
  addLeaves(root.left);
  addLeaves(root.right);
  final rightStack = <T>[];
  addRightBoundary(root.right, rightStack);
  for (var i = rightStack.length - 1; i >= 0; --i) {
    result.add(rightStack[i]);
  }
  return result;
}