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.

Question

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.

My codes of the iterator implementation · Accepted Answer

class TreeNode { public: int val; TreeNode *left; TreeNode *right; TreeNode(int val) : val(val), left(NULL), right(NULL) {} }; class TreeIterator { private: stack

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

In-order tree traversal w/out recursion in PHP · Answer

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

Meta

Question d’entretien chez Meta

Réponses aux questions d'entretien

Entreprises suivies

Recherche d’emplois