Two Sum BSTs

LeetCode Link

Problem Description

Visit LeetCode for the full problem description.

---

Solutions

Solution 1: C# (Best: 224 ms)

Metric	Value
Runtime	224 ms
Memory	40.9 MB
Date	2022-01-04

Solution

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
public class Solution {
    public bool TwoSumBSTs(TreeNode root1, TreeNode root2, int target) {
        if(root1 == null || root2 == null)
        return false;
    Stack<TreeNode> s1 = new Stack<TreeNode>();
    Stack<TreeNode> s2 = new Stack<TreeNode>();
    TreeNode t1, t2;
    
    while(true)
    {
        while(root1 != null)
        {
            s1.Push(root1);
            root1 = root1.left;
        }
        while(root2 != null)
        {
            s2.Push(root2);
            root2 = root2.right;
        }
        if(s1.Count ==0 || s2.Count == 0)
        break;
        t1 = s1.Peek();
        t2 = s2.Peek();
        int sum = t1.val + t2.val;
        if(sum == target) return true;
        else if(sum < target)
        {
            s1.Pop();
            root1 = t1.right;
        }
        else
        {
            s2.Pop();
            root2 = t2.left;
        }
    }
    
    return false;
    }
}

---

Complexity Analysis

Approach	Time	Space
Solution	To be analyzed	To be analyzed