Tree traversal: Difference between revisions

Content added Content deleted

Inline

@@ Line 10,324: / Line 10,324: @@
     }
-    // Leftmost to rightmost
+    // From left to right
     fn iterative_inorder(&self) -> Vec<&TreeNode<T>> {
         let mut stack: Vec<&TreeNode<T>> = Vec::new();
         let mut res: Vec<&TreeNode<T>> = Vec::new();
-        let mut p = self;
+        let mut option_tree = Some(self);
-        loop {
+        while {
-            // Stack parents and right children while left-descending
+           // Descend leftwards
-            loop {
+            while let Some(tree) = option_tree {
-                match p.right {
+                stack.push(tree);
-                    None => {}
+                option_tree = tree.left.as_deref();
-                    Some(box ref n) => stack.push(n),
-                }
-                stack.push(p);
-                match p.left {
-                    None => break,
-                    Some(box ref n) => p = n,
-                }
-            }
-            // Visit the nodes with no right child
-            p = stack.pop().unwrap();
-            while !stack.is_empty() && p.right.is_none() {
-                res.push(p);
-                p = stack.pop().unwrap();
-            }
-            // First node that can potentially have a right child:
-            res.push(p);
-            if stack.is_empty() {
-                break;
-            } else {
-                p = stack.pop().unwrap();
             }
+            !stack.is_empty()
+        } {
+            let tree = stack.pop().unwrap();
+            res.push(tree);
+            option_tree = tree.right.as_deref();
         }
         res