Two Sum IV - Input is a BST — LeetCode 653 Python Solution
EasyTreeDepth-First SearchBreadth-First SearchBinary Search TreeHash TableTwo PointersBinary Tree
- Problem
- #653
- Pattern
- Two Pointers
- Reading time
- 3 min
- Source
- leetcode.com
The problem
Given the root of a binary search tree and an integer k, return true if there exist two elements in the BST such that their sum is equal to k, or false otherwise.
Example
- Input
- root = [5,3,6,2,4,null,7], k = 9
- Output
- true
Python solution
Python
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
def dfs(root):
if root is None:
return False
if k - root.val in vis:
return True
vis.add(root.val)
return dfs(root.left) or dfs(root.right)
vis = set()
return dfs(root)Complexity
| Measure | Complexity |
|---|---|
| Time | O(n) |
| Space | O(n) auxiliary |
Pattern: Two Pointers
Use the order already in the input to discard half the search space at every step. LeetCode 653. Two Sum IV - Input is a BST is filed here because LeetCode tags it Two Pointers, which is the vocabulary this hub collects.
The two pointers guide has the Python template for the pattern and the 201 LeetCode problems that use it.
Related problems
LeetCode 1Two SumEasyLeetCode 863All Nodes Distance K in Binary TreeMediumLeetCode 865Smallest Subtree with all the Deepest NodesMediumLeetCode 987Vertical Order Traversal of a Binary TreeHardLeetCode 1123Lowest Common Ancestor of Deepest LeavesMediumLeetCode 1261Find Elements in a Contaminated Binary TreeMedium
Frequently asked questions
- How hard is LeetCode 653. Two Sum IV - Input is a BST?
- LeetCode 653. Two Sum IV - Input is a BST is rated Easy on LeetCode.
- What is the time complexity of LeetCode 653. Two Sum IV - Input is a BST?
- The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 653. Two Sum IV - Input is a BST?
- The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 653. Two Sum IV - Input is a BST cover?
- LeetCode 653. Two Sum IV - Input is a BST is tagged Tree, Depth-First Search, Breadth-First Search, Binary Search Tree, Hash Table, Two Pointers and Binary Tree on LeetCode.