day112

Documentation

Index

• type Node
  • func LowestCommonAncestor(n1, n2 *Node) *Node

Types

type Node

type Node struct {
	Parent *Node
}

Node has a pointer to its parent.

func LowestCommonAncestor

func LowestCommonAncestor(n1, n2 *Node) *Node

LowestCommonAncestor returns the lowest common ancestor. Returns nil if the two nodes don't share a common node. Assumes the graph is a DAG. Any cycles returns nil. Runs in O(N) time and stores 1 path so technically O(N) memory.