LCA in Binary Tree
LCA

LCA in Binary Tree

Today I will be writing about the LCA(Least Common Ancestor) for a binary tree.

LCA refers to the node in the binary tree, which is the common ancestor and is closest to the two given nodes or farthest from the root node, yes LCA is defined for two other existing nodes in a binary tree.

Let us quickly jump into the algorithm.

In this algorithm, we check the node we are at, if it is equal to any of the node value for which we are finding the LCA, we simply return it.

Otherwise we check the left and right halves recursively, and if we get both as non null, that means this node is the LCA of the two nodes . Else return the non null part either it can be the left or the right. In this algorithm it is assumed that both the nodes are already present in the tree. For better understanding draw the recursive stacks and dry run the sample tree given in my code.

Please take a look at my code -

LCA code

I keep sharing such content on DSA and Android Developement regularly, do follow me for more such content. Happy Coding.


要查看或添加评论,请登录

Siddhant Mishra的更多文章

  • SuspendCoroutine

    SuspendCoroutine

    Today I will be writing about the usage of an important concept in Android namely suspendCoroutine. By definition…

  • findViewById - Internals

    findViewById - Internals

    Hope everyone is doing well. Today I will be writing about the internal working of findViewById in Android.

    2 条评论
  • Lambda functions

    Lambda functions

    Today I will be writing about two different yet intriguing way to write the lambda functions in Kotlin. Conventionally…

    1 条评论
  • Exceptions in Coroutines

    Exceptions in Coroutines

    Hi everyone, today I will be writing about exceptions in Coroutine and how to handle them gracefully. First let us see…

  • Trie data structure

    Trie data structure

    Today I will write about a magical data structure namely Trie. When we talk of storing and retriving some information…

  • Vertical Order traversal in binary tree

    Vertical Order traversal in binary tree

    We generally talk about Inorder, PreOrder, PostOrder and LevelOrder traversals in binary tree, but we generally do not…

  • Delegates in Kotlin

    Delegates in Kotlin

    Today I will be writing about my understanding regarding the delegates in Kotlin. The english meaning of Delegation…

  • TypeAlias in Kotlin

    TypeAlias in Kotlin

    Today I will be writing about TypeAlias in Kotlin and how do I understand and use it in my day to day coding. Typealias…

  • Reified in Kotlin

    Reified in Kotlin

    Today I will be writing about the type erasure in Java and Kotlin and its solution. The concept of type erasure stems…

    1 条评论
  • Jetpack Compose - Interesting features to dive deeper into.

    Jetpack Compose - Interesting features to dive deeper into.

    Recently I got to migrate my sample project from the conventional XML to Jetpack Compose, and I would like to list down…

    3 条评论

社区洞察

其他会员也浏览了