iwburns · Aug 22, 2023 · Aug 22, 2023
Showing with 15 additions and 5 deletions.

+15 −5 src/tree.rs
diff --git a/src/tree.rs b/src/tree.rs
@@ -1,4 +1,5 @@
 use std::cmp::Ordering;
+use std::collections::VecDeque;
 
 use super::snowflake::ProcessUniqueId;
 use super::*;
@@ -200,20 +201,29 @@ impl<T> Tree<T> {
     /// assert_eq!(2, tree.height());
     /// ```
     ///
+    #[inline(always)]
     pub fn height(&self) -> usize {
         match self.root {
             Some(ref id) => self.height_of_node(id),
             _ => 0,
         }
     }
 
+    #[inline(always)]
     fn height_of_node(&self, node: &NodeId) -> usize {
-        let mut h = 0;
-        for n in self.children_ids(node).unwrap() {
-            h = std::cmp::max(h, self.height_of_node(n));
+        let mut h = 1;
+        let mut to_process = VecDeque::new();
+
+        to_process.push_back((h, node));
+        while !to_process.is_empty() {
+            let (next_h, id) = to_process.pop_front().unwrap();
+            self.children_ids(id).unwrap().for_each(|child_id| {
+                to_process.push_back((next_h + 1, child_id));
+                h = std::cmp::max(h, next_h + 1);
+            });
         }
-
-        h + 1
+        
+        h
     }
 
     /// Inserts a new `Node` into the `Tree`.  The `InsertBehavior` provided will determine where