101. Symmetric Tree
Symmetric Tree (LeetCode 101) is a Easy Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
How to solve Symmetric Tree
Symmetric Tree is a Preorder Traversal problem, part of Tree Traversal Patterns (DFS & BFS). Master preorder traversal for tree construction, inversion, and path problems. Visit root before children.
Work towards the solution in these steps:
- Consider which tree traversal techniques can help you compare nodes systematically on both sides of the tree.
- Think about how you can traverse the left and right subtrees simultaneously to check for symmetry.
- Try to define a helper function that compares two nodes and recursively checks if their subtrees are mirrors of each other.
The reference solution runs in O(n) time and O(h) space.
The Symmetric Tree solution and editorial walks through the full approach with reference code.
Problem statement
Given the root of a binary tree, check whether it is a mirror of itself (i.e., symmetric around its center).
Example 1:
Input: root = [1,2,2,3,4,4,3] Output: true
Example 2:
Input: root = [1,2,2,null,3,null,3] Output: false
Constraints:
- The number of nodes in the tree is in the range [1, 1000].
- -100 <= Node.val <= 100
Follow up: Could you solve it both recursively and iteratively?
Topics and companies
Topics: Tree, Depth-First Search, Breadth-First Search, Binary Tree.
Reported in interviews at Capital One, Amazon, Yandex, Apple, Uber, Google, Microsoft.
How to practise Symmetric Tree on Thita.ai
Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(h) space.
Open Symmetric Tree in the code editor, or read the Symmetric Tree editorial for a worked solution with its approach and complexity analysis.
Where Symmetric Tree sits in the DSA pattern sheet
- Tree Traversal Patterns (DFS & BFS) pattern guide
- Recursive Preorder Traversal subpattern
- The full DSA patterns sheet
Problems related to Symmetric Tree
Other problems that use the same Recursive Preorder Traversal and Tree Traversal Patterns (DFS & BFS) techniques:
- Binary Tree Paths — Easy, same subpattern
- Binary Tree Preorder Traversal — Easy, same subpattern
- Construct Binary Tree from Preorder and Inorder Traversal — Medium, same subpattern
- Construct Quad Tree — Medium, same subpattern
- Count Good Nodes in Binary Tree — Medium, same subpattern
- Flatten Binary Tree to Linked List — Medium, same subpattern
Symmetric Tree FAQ
What is the LeetCode number of Symmetric Tree?
Symmetric Tree is LeetCode problem 101, rated Easy.
What pattern is used to solve Symmetric Tree?
Symmetric Tree is a Preorder Traversal problem. It belongs to the Tree Traversal Patterns (DFS & BFS) pattern, in the Recursive Preorder Traversal subpattern.
What is the time complexity of Symmetric Tree?
The reference solution runs in O(n) time and O(h) space.
Which companies ask Symmetric Tree?
Symmetric Tree has been reported in interviews at Capital One, Amazon, Yandex, Apple, Uber, Google, Microsoft.