leetcode

commit 20caf1440591f722863e4de9da3402ffc9da8204
parent 8614a5600e2a0f02eed9ddf469fd718554a90642
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Fri,  2 Jun 2023 10:02:50 -0500

Completede cousins in binary tree

Diffstat:
A
cousins-in-binary-tree/cousins-in-binary-tree.dart
 | 
44
++++++++++++++++++++++++++++++++++++++++++++

1 file changed, 44 insertions(+), 0 deletions(-)
diff --git a/cousins-in-binary-tree/cousins-in-binary-tree.dart b/cousins-in-binary-tree/cousins-in-binary-tree.dart
@@ -0,0 +1,44 @@
+//Given a binary tree return if the nodes with values
+//x and y are cousins meaning they are at the same depth
+//but do not have the same parent nodes. 
+
+//To solve this I used DFS to find the depth of the respective nodes, and
+//the parent of the target nodes.
+//I then compared them to see if they were the same. If they are then they are
+//not cousins if they are not then they are.
+
+//Time: 300ms Beats: 100%
+//Memory: 142.9MB Beats: 100%
+
+class Solution {
+  bool isCousins(TreeNode? root, int x, int y) {  
+      CurrNode? x_node = searchForNode(root,x,0,null);
+      CurrNode? y_node = searchForNode(root,y,0,null);
+      if(x_node == null || y_node == null){
+          return false;
+      }
+      if(x_node.depth != y_node.depth || x_node.parent == y_node.parent){
+          return false;
+      }
+      return true;
+}
+    CurrNode? searchForNode(TreeNode? root, int target, int depth , TreeNode? parent){
+        if(root == null){
+            return null;
+        }
+        if(root.val == target){
+            return CurrNode(parent, depth);
+        }
+        CurrNode? left = searchForNode(root.left, target, depth + 1 , root);
+        CurrNode? right = searchForNode(root.right, target, depth + 1 , root);
+        if(left != null){
+            return left;
+        }
+        return right;
+    }
+}
+class CurrNode{
+    TreeNode? parent;
+    int depth;
+    CurrNode( this.parent, this.depth);
+}