Symmetric Tree

Solution in Go

Recursive #

func isSymmetric(root *TreeNode) bool {
    return check(root.Left, root.Right)
}

func check(left *TreeNode, right* TreeNode) bool {
    if left == nil && right == nil {
        return true
    }

    if (left == nil && right != nil) || (left != nil && right == nil) || (left.Val != right.Val) {
        return false
    }

    return check(left.Right, right.Left) && check(left.Left, right.Right)
}

Non-Recursive (using Stack) #

func isSymmetric(root *TreeNode) bool {
    stack := NewStack[*TreeNode]()

    stack.Push(root.Left)
    stack.Push(root.Right)

    for !stack.IsEmpty() {
        right := stack.Pop()
        left := stack.Pop()

        // Structural mismatch
        if (right != nil && left == nil) || (right == nil && left != nil) {
            return false
        }

        if left == nil && right == nil {
            continue
        }

        // Value is not same
        if right.Val != left.Val {
            return false
        }

        stack.Push(left.Right)
        stack.Push(right.Left)
        stack.Push(left.Left)
        stack.Push(right.Right)
    }

    return true
}

type Stack[T any] struct {
    arr []T
}

func NewStack[T any]() *Stack[T] {
    return &Stack[T]{
        arr: []T{},
    }
}

func (s *Stack[T]) Push(v T) {
    s.arr = append(s.arr, v)
}

func (s *Stack[T]) Pop() T {
    v := s.arr[len(s.arr) - 1]
    s.arr = s.arr[:len(s.arr) - 1]
    return v
}

func (s *Stack[T]) IsEmpty() bool {
    return len(s.arr) == 0
}
Subscribe via email

Get notified once/twice per month when new articles are published.

Copyright © 2022 - 2024 TheDeveloperCafe.
The Go gopher was designed by Renee French.