Binary tree node with pointer to siblings in Rust

Question

I am trying to figure out the equivalent of the typical setSibling C code exercise:

// Assume the tree is fully balanced, i.e. the lowest level is fully populated.
struct Node {
   Node * left;
   Node * right;
   Node * sibling;
}

void setSibling(Node * root) {
   if (!root) return;
   if (root->left) {
      root->left->sibling = root->right;
      if (root->sibling) root->right->sibling = root->sibling->left;
      SetSibling(left);
      SetSibling(right);
   }
}

Of course Rust is a different world, so I am forced to think about ownership now. My lousy attempt.

struct TreeNode<'a> {
    left: Option<&'a TreeNode<'a>>,
    right: Option<&'a TreeNode<'a>>,
    sibling: Option<&'a TreeNode<'a>>,
    value: String
}

fn BuildTreeNode<'a>(aLeft: Option<&'a TreeNode<'a>>, aRight: Option<&'a TreeNode<'a>>, aValue: String) -> TreeNode<'a> {
    TreeNode {
        left: aLeft,
        right: aRight,
        value: aValue,
        sibling: None
    }
}

fn SetSibling(node: &mut Option<&TreeNode>) {
    match node {
        Some(mut n) => {
            match n.left {
                Some(mut c) => {
                    //c*.sibling = n.right;
                    match n.sibling {
                        Some(s) => { n.right.unwrap().sibling = s.left },
                        None => {}
                    }
                },
                None => {}
            }
        },
        None => return
    }
}

What's the canonical way to represent graph nodes like these?

Answer 1

Question: what's the canonical way to represent graph nodes like these?

It seems like a typical case of "confused ownership" once you introduce the sibling link: with a strict tree you can have each parent own its children, but the sibling link means this is a graph, and a given node has multiple owners.

AFAIK there are two main ways to resolve this, at least in safe Rust

• reference counting and inner mutability, if each node is reference-counted, the sibling link can be a reference or weak reference with little trouble, the main drawbacks are this requires inner mutability and the navigation is gnarly, though a few utility methods can help
• "unfold" the graph into an array, and use indices for your indirection through the tree, the main drawback is this requires either threading or keeping a backreference (with inner mutability) to the array, or alternatively doing everything iteratively

Both basically work around the ownership constraint, one by muddying the ownership itself, and the other by moving ownership to a higher power (the array).

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=68d092d0d86dc32fe07902c832262ef4 seems to be more or less what you're looking using Rc & inner mutability:

use std::cell::RefCell;
use std::rc::{Rc, Weak};

#[derive(Default)]
pub struct TreeNode {
    left: Option<Rc<TreeNode>>,
    right: Option<Rc<TreeNode>>,
    sibling: RefCell<Option<Weak<TreeNode>>>,
    v: u8,
}

impl TreeNode {
    pub fn new(v: u8) -> Rc<Self> {
        Rc::new(TreeNode {
            v,
            ..TreeNode::default()
        })
    }
    pub fn new_with(left: Option<Rc<TreeNode>>, right: Option<Rc<TreeNode>>, v: u8) -> Rc<Self> {
        Rc::new(TreeNode {
            left,
            right,
            v,
            sibling: RefCell::new(None),
        })
    }
    pub fn set_siblings(self: &Rc<Self>) {
        let Some(left) = self.left() else { return };
        let right = self.right();

        left.sibling.replace(right.map(Rc::downgrade));

        if let Some(sibling) = self.sibling() {
            // not sure this is correct, depending on construction, with
            // 3  5
            //  \  \
            //  2  4
            //   \/
            //   1
            // (2) has a sibling (4) but doesn't have a right node, so 
            // unconditionally setting right.sibling doesn't seem correct
            right
                .unwrap()
                .sibling
                .replace(sibling.left().map(Rc::downgrade));
        }

        left.set_siblings();
        right.map(|r| r.set_siblings());
    }

    pub fn left(&self) -> Option<&Rc<Self>> {
        self.left.as_ref()
    }
    pub fn right(&self) -> Option<&Rc<Self>> {
        self.right.as_ref()
    }
    pub fn sibling(&self) -> Option<Rc<Self>> {
        self.sibling.borrow().as_ref()?.upgrade()
    }
}

fn main() {
    let t = TreeNode::new_with(
        TreeNode::new_with(TreeNode::new(1).into(), TreeNode::new(2).into(), 3).into(),
        TreeNode::new(4).into(),
        5,
    );
    t.set_siblings();

    assert_eq!(t.left().and_then(|l| l.sibling()).unwrap().v, 4);
    let ll = t.left().and_then(|l| l.left());
    assert_eq!(ll.map(|ll| ll.v), Some(1));
    ll.unwrap().sibling().unwrap();
    assert_eq!(
        t.left()
            .and_then(|l| l.left())
            .and_then(|ll| ll.sibling())
            .unwrap()
            .v,
        2
    );
}

Note that I assumed the tree is immutable once created, only the siblings links have to be generated post-facto. So I only added inner mutability for those. I also used weak pointers which probably isn't necessary, if the tree is put in an inconsistent state it's not like that'll save anything. All it requires is a few upgrade() and downgrade() calls in stead of clone() though so it's not a huge imposition.

That aside, there are lots of issues with your attempt:

• having the same lifetime for your reference and your content is usually an error, the compiler will trust what you tell it, and that can have rather odd effects (e.g. of telling the compiler that something gets borrowed forever)
• SetSibling (incorrect naming conventions btw) taking an Option is... unnecessary, function clearly expects to set a sibling, just give it a sibling, and remove the unnecessary outer layer of tests
• match is nice, when you need it. Here, you probably don't, if let would do the trick fine especially since there is no else branch
• rust generally uses methods, and the method to create an instance (if one such is needed) is idiomatically called new (if there's only one)