スタックを使用してツリーをトラバースするとき、ツリーの深さをどのように追跡するのですか？

Question

私はこのようなスタックを使用して、ツリートラバーサルアルゴリズムしている場合：

input: root 
push root onto stack 
while stack not empty: 
    pop current node off stack 
    mark current as visited 
    for each of current node's successors: 
     if successor not visited: 
      push successor onto stack 

を、私は私のツリーの最大の深さを与えるために、このアルゴリズムを変更することができる簡単な方法はありますか？私は再帰を使用している場合、それを行う方法を考えることができますが、私はスタックメソッドを使用してそれを行う方法を考えてちょっと立ち往生しています。

Answer 1

ノードとその深さをスタックにプッシュし、それまでに見た深さを最大限に追跡することができます。

input: root 
push (root, 0) onto stack 
max_depth = 0 
while stack not empty: 
    pop current (node, depth) off stack 
    if depth > max_depth: 
     max_depth = depth 
    mark current as visited 
    for each of current node's successors: 
     if successor not visited: 
      push (successor, depth+1) onto stack 

return max_depth