algorithms

README

Same Tree

Problem

Given the roots of two binary trees p and q, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.

Example

Input: p = [1,2,3], q = [1,2,3]

Output: true

Input: p = [1,2], q = [1,null,2]

Output: false

Solution

Recursive Solution

The recursive solution is pretty straightforward. We check if both nodes are nil and return true if they are. If both nodes are not nil, we check if their values are equal and if the left and right subtrees are equal. Otherwise, we return false.

Code

Go

func IsSameTreeRecursive(p *TreeNode, q *TreeNode) bool {
    if p == nil && q == nil {
        return true
    }

    if p != nil && q != nil {
        return p.Val == q.Val && IsSameTreeRecursive(p.Left, q.Left) && IsSameTreeRecursive(p.Right, q.Right)
    }

    return false
}

Complexity Analysis

• Time Complexity : O(n), where n is the number of nodes in the tree. We have to visit each node at least once.

• Space Complexity : O(n). The number of recursive calls is bound by the height of the tree. In the worst case, the tree is linear and the height is in O(n). Therefore, space complexity due to recursive calls on the stack is O(n) in the worst case.

Documentation

Index

• func IsSameTreeRecursive(p *TreeNode, q *TreeNode) bool
• type TreeNode

Functions

func IsSameTreeRecursive

func IsSameTreeRecursive(p *TreeNode, q *TreeNode) bool

Recursive solution

Types

type TreeNode

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

Definition for a binary tree node