iOS, Find least common ancestor from 2 UIViews

Find the least common ancestor.

UIView is a tree data structure. Each node (UIView) can have multiple subviews.

To find the least common ancestor, You can use either recursive calling or using a superview property.

UIView provide a useful functions and properties

subviews: [UIView]
superview: UIView?
func isDescendant(of: UIView) -> Bool

Let’s create a View Trees.

 @discardableResult
    func insertView(_ at: UIView, tag: Int) -> UIView {
        let node = UIView()
        node.tag = tag
        at.addSubview(node)
        return node
    }

func setupViewTree() {
        //insert level 1
        let tag0view = insertView(view, tag: 11)
        insertView(view, tag: 1)
        let tag2view = insertView(view, tag: 2)
        
        //insert level 2
        insertView(tag0view, tag: 3)
        let tag4view = insertView(tag0view, tag: 4)
        
        insertView(tag2view, tag: 5)
        let tag6view = insertView(tag2view, tag: 6)
        insertView(tag2view, tag: 7)
        
        //insert level 3
        insertView(tag4view, tag: 8)
        insertView(tag6view, tag: 9)
    }

Helper function – Find a view with Tag

func findView(_ at: UIView, tag: Int) -> UIView? {
        //Base case
        if at.tag == tag {
            return at
        }
        guard !at.subviews.isEmpty else {
            return nil
        }
        let subviews = at.subviews
        var targetView: UIView?
        for subview in subviews {
            if let view = findView(subview, tag: tag) {
                targetView = view
                break
            }
        }
        return targetView
    }

Approach 1. Use Recursive Call

If you want to see this logic step by step then visit my previous post.

This approach is start from rootView. So we have to know what’s the root view.

Swift, Data Structure – Tree Structure

func findLeastCommonParentFromRootView(rootView: UIView, targetView1: UIView?, targetView2: UIView?) -> UIView? {
        guard let targetView1, let targetView2 else {
            return nil
        }
        return recursiveFindLeastCommonParentUsing(
            rootView: rootView,
            targetView1: targetView1,
            targetView2: targetView2
        )
    }


private func recursiveFindLeastCommonParentUsing(
        rootView: UIView?,
        targetView1: UIView,
        targetView2: UIView
    ) -> UIView? {
        guard let rootView else {
            return nil
        }
        //Base case, prevent search targetView's childs
        if rootView == targetView1 || rootView == targetView2 {
            return rootView
        }
        let subviews = rootView.subviews
        var ancestors = [UIView]()
        for view in subviews {
            if let ancestorView = recursiveFindLeastCommonParentUsing(rootView: view, targetView1: targetView1, targetView2: targetView2) {
                ancestors.append(ancestorView)
            }
        }
        if ancestors.contains(targetView1), ancestors.contains(targetView2) {
            return rootView
        }
        if ancestors.isEmpty {
            return nil
        }
        return ancestors.last
    }

Approach 2. Use superview

This approach is much simpler than approach 1. It uses a superview. Not calling a function recursively.

private func findLeastCommonParentWithoutRootView(targetView1: UIView?, targetView2: UIView?) -> UIView? {
        guard targetView1 != nil, targetView2 != nil else {
            return nil
        }
        var target1 = targetView1
        var target2 = targetView2
        
        while target1?.superview != nil, target2?.superview != nil {
            let targetView1SuperView = target1?.superview
            var targetView2SuperView = target2?.superview
            while targetView2SuperView?.superview != nil {
                if targetView1SuperView == targetView2SuperView {
                    return targetView2SuperView
                }
                targetView2SuperView = targetView2SuperView?.superview
            }
            target1 = target1?.superview
            target2 = target2?.superview
        }
        
        if target1?.subviews != nil {
            while target1?.superview != nil {
                target1 = target1?.superview
            }
        }
        if target2?.subviews != nil {
            while target2?.superview != nil {
                target2 = target2?.superview
            }
        }
        if target1 == target2 {
            return target1
        }
        else {
            return nil
        }
    }

If each target view’s rootView is different then It will returns nil

Approach 3. Use isDescendant

func findLeastCommonParentUsingIsDescendantView(rootView: UIView, targetView1: UIView?, targetView2: UIView?) -> UIView? {
        guard let targetView1, let targetView2 else {
            return nil
        }
        var root: UIView = rootView
        var stack = [UIView]()
        //Base case
        guard targetView1.isDescendant(of: root), targetView2.isDescendant(of: root) else {
            return nil
        }
        while !root.subviews.isEmpty {
            for subview in root.subviews {
                if targetView1 != subview, targetView1.isDescendant(of: subview), targetView2 != subview, targetView2.isDescendant(of: subview) {
                    stack.append(subview)
                }
            }
            if let last = stack.last, root != last {
                root = last
            }
            else {
                break
            }
        }
        return stack.last ?? root
    }

Test all 3 approaches

 override func viewDidLoad() {
        super.viewDidLoad()
        setupViewTree()
        let result = findLeastCommonParentFromRootView(
            rootView: view,
            targetView1: findView(view, tag: 5),
            targetView2: findView(view, tag: 9)
        )
        print("🟢 Approach 1 Least common parent: \(result?.tag)")
        
        let result2 = findLeastCommonParentWithoutRootView(
            targetView1: findView(view, tag: 5),
            targetView2: findView(view, tag: 9)
        )
        print("🟢 Approach 2  Least common parent: \(result2?.tag)")
        
        let result3 = findLeastCommonParentUsingIsDescendantView(
            rootView: view,
            targetView1: findView(view, tag: 5),
            targetView2: findView(view, tag: 9)
        )
        print("🟢 Approach 3  Least common parent: \(result3?.tag)")
    }

Shawn