🚀 Optimized Implicit Reconstruction || 0ms in Rust & Go || O(log target) Time and Space
Intuition 🤔Instead of explicitly reconstructing the tree, we leverage the given rules torecursively navigateand determine iftargetexists.Each node’s value follo
# Intuition 🤔

Instead of explicitly reconstructing the tree, we leverage the given rules to __recursively navigate__ and determine if `target` exists. 
Each node’s value follows a strict formula, so we can compute its __parent's value__ and check if the target node should exist.

# Approach 🔍

- __Recursive Parent Lookup:__
    - Start from target, compute its parent value using $\frac{target - 1}{2}$.
    - Recursively find the __parent node__ first.
    - If the parent doesn't exist, $target$ cannot exist.

2. __Determine Left/Right Child:__
    - If ${target-1}\mod 2 = 0$ → result is left child.
    - Otherwise, it's the right child.

3. __Return Node if Found:__
    - If the correct child exists, return it; otherwise, return $None$.

# Complexity Analysis 📊

- __Time Complexity:__ $O(\log target)$ 🕒
    - Each recursive call moves one level up (dividing target by 2).
    - Maximum depth is $\log(target)$.

- __Space Complexity:__ $O(\log target)$ 📦
    - Recursive stack depth is at most $\log(target)$.
    - No extra memory is used for storing values.Complexity


# Code
```rust []
use std::rc::Rc;
use std::cell::RefCell;
struct FindElements {
    root: Option<Rc<RefCell<TreeNode>>>
}


impl FindElements {

    fn new(root: Option<Rc<RefCell<TreeNode>>>) -> Self {
        FindElements { root }
    }
    
    // Checks if the target value exists in the tree
    pub fn find(&self, target: i32) -> bool {
        find_recursive(self.root.clone(), target).is_some()
    }
}

// Recursively finds the target node by first locating its parent
fn find_recursive(node: Option<Rc<RefCell<TreeNode>>>, target: i32) -> Option<Rc<RefCell<TreeNode>>> {
    if target == 0 {
        return node; // Base case: root is always at value 0
    }

    let parent_val = (target - 1) / 2;
    match (target - 1) % 2 {
        0 => find_recursive(node, parent_val)?.borrow().left.clone(),
        1 => find_recursive(node, parent_val)?.borrow().right.clone(),
        _ => unreachable!("unexpected mod 2 value")
    }
}
```
``` golang []
type FindElements struct {
    Root *TreeNode
}

// Constructor: Simply stores the root without modifying the tree
func Constructor(root *TreeNode) FindElements {
    return FindElements{Root: root}
}

// Checks if the target value exists in the tree
func (this *FindElements) Find(target int) bool {
    return findRecursive(this.Root, target) != nil
}

// Recursively finds the target node by first locating its parent
func findRecursive(node *TreeNode, target int) *TreeNode {
    if target == 0 {
        return node // Base case: root is always at value 0
    }

    // Compute the parent's value
    parentVal := (target - 1) / 2
    parent := findRecursive(node, parentVal)

    if parent == nil {
        return nil // If parent does not exist, target cannot exist
    }

    // Determine if target is the left or right child
    if (target-1)%2 == 0 {
        return parent.Left
    }
    return parent.Right
}
```
``` racket []
; Definition for a binary tree node.
#|

; val : integer?
; left : (or/c tree-node? #f)
; right : (or/c tree-node? #f)
(struct tree-node
  (val left right) #:mutable #:transparent)

; constructor
(define (make-tree-node [val 0])
  (tree-node val #f #f))

|#

(define find-elements%
  (class object%
    (super-new)

    ; root : (or/c tree-node? #f)
    (init-field root)

    ; Recursively finds the target node by first locating its parent
    (define/private (find-recursive node target)
      (cond
        [(zero? target) node] ; Base case: root is always 0
        [else
         (let* ([parent-val (quotient (- target 1) 2)]
                [parent (find-recursive node parent-val)])
           (cond
             [(not parent) #f] ; Parent doesn't exist, so target can't exist
             [(even? (- target 1)) (tree-node-left parent)] ; Left child case
             [else (tree-node-right parent)]))])) ; Right child case

    ; Finds if the target value exists in the tree
    (define/public (find target)
      (not (not (find-recursive root target))))))
```
['Recursion', 'Binary Tree', 'Go', 'Rust', 'Racket']