Engaged Employer

Interview

# Create an iterator to traverse a binary tree. When the next

function is called on the binary tree return the value at the next node as if you are doing an inorder traversal of the tree. Restrictions: Nodes do not have pointers to their parent node and you can't use recursion.

2

class TreeNode { public: int val; TreeNode *left; TreeNode *right; TreeNode(int val) : val(val), left(NULL), right(NULL) {} }; class TreeIterator { private: stack<TreeNode*> stackA; public: TreeIterator(TreeNode *root = NULL){ while (root){ stackA.push(root); root = root->left; } } TreeNode* getNext(){ if (stackA.empty()) return NULL; TreeNode *target = stackA.top(); stackA.pop(); TreeNode *node = target->right; while (node){ stackA.push(node); node = node->left; } return target; } };

My codes of the iterator implementation on Oct 5, 2014
0

<?php class Node implements \IteratorAggregate { /** @var mixed */ public \$value; /** @var Node */ public \$left; /** @var Node */ public \$right; function __construct(\$data, \$left=null, \$right=null) { \$this->left = \$left; \$this->right = \$right; \$this->value = \$data; } public function getIterator() { \$it = \$this; \$stack = []; while(\$it) { \$stack[] = \$it; \$it = \$it->left; } while(\$stack) { \$it = array_pop(\$stack); yield \$it->value; \$it = \$it->right; while(\$it) { \$stack[] = \$it; \$it = \$it->left; } } } } function printStack(\$arr) { echo implode(' ',array_map(function(\$n) { return \$n->value; }, \$arr)).PHP_EOL; } \$tree = new Node(1, new Node(2, new Node(4, new Node(8), new Node(9) ), new Node(5, new Node(10), new Node(11) ) ), new Node(3, new Node(6/*, new Node(12), new Node(13)*/ ), new Node(7/*, new Node(14), new Node(15)*/ ) ) ); foreach(\$tree as \$value) { echo \$value.' '; }

In-order tree traversal w/out recursion in PHP on May 20, 2015