1
$\begingroup$

You're given a single root node to grow a binary tree. The generation of the left and right child is random and independent, with probability of 1/2, respectively. What's the probability of you ending up with a symmetrical tree?

Edit:

Here "symmetrical" means visual symmetry by the vertical centerline starting from the root
Example of symmetrical tree:

    *
   / \
  *   *
   \ /
   * *

My thinking is:

let p be the probability of a pair of symmetrical nodes having symmetrical children, starting from 3-node case.

     root 
       * 
      / \
     *   * 
  left   right

Then

$p=\frac{1}{16}+\frac{2}{16}p + \frac{2}{16}p^2$

$\frac{1}{16}$: case of termination, no children generated on both left and right node.

$\frac{2}{16}p$: case of left and right having single child and they're symmetrical, pair number stay the same

$\frac{1}{16}p^2$: case of full children for both left and right node, pair number increases to 2, independently each pair continue the the generation, hence $p^2$

Then final probability equals $\frac{1}{4}(1+p)$ starting from root node because it has 1/4 chance having no child and 1/4 having left and right node.

The final result is $2-\sqrt{3}$

$\endgroup$
3
  • $\begingroup$ Welcome to Mathematics SE. Take a tour. You'll find that simple "Here's the statement of my question, solve it for me" posts will be poorly received. What is better is for you to add context (with an edit): What you understand about the problem, what you've tried so far, etc.; something both to show you are part of the learning experience and to help us guide you to the appropriate help. You can consult this link for further guidance. $\endgroup$ Commented Feb 19, 2023 at 15:47
  • $\begingroup$ At each "step" in a binary tree, there is a 1/2 probability that it continues being a symmetrical tree. You can visualize this by setting the node on the right side, and showing that the left side has a 1/2 probability to stay symmetrical. So the probability is (1/2)^n, if there are n steps. $\endgroup$ Commented Feb 19, 2023 at 15:50
  • $\begingroup$ Does the graph have to be visually symmetric e.g. LL vs RR or is it enough for it to be balanced so e.g. LL is balanced by either RR or RL? $\endgroup$
    – Laska
    Commented Feb 19, 2023 at 15:56

1 Answer 1

1
$\begingroup$

Unfortunately I was unable to follow your thought process, so I’ll just say how I’d solve the problem.

The tree is symmetric if its two branches are mirror images of each other, and the probability for that is the same as the probability that they’re identical. So you want to know the probability $p$ that two branches are identical. This occurs either if both branches have no nodes, with probability $\frac12\cdot\frac12=\frac14$, or if both branches have a node and those two nodes have the same left branches and the same right branches, with probability $\frac12\cdot\frac12\cdot p\cdot p$. So

$$ p=\frac14+\frac14p^2\;, $$

or $p^2-4p+1=0$, with solutions $p=2\pm\sqrt3$, and the solution in $[0,1]$ is the desired probability $p=2-\sqrt3\approx0.268$. So the probability isn’t much more than the probability $\frac14$ of both branches not existing at all, because if they do exist, it’s rather unlikely that they’ll be mirror images.

$\endgroup$
7
  • $\begingroup$ Thanks joriki. Isn't your p*p the probability of left child itself has identical branches and right child itself has identical/mirror braches. This doesn't gurantee mirroring from the root node. $\endgroup$
    – Albert
    Commented Feb 20, 2023 at 10:12
  • $\begingroup$ @Albert: No. $p^2$ is the probability $p$ that the left branch of the left child is identical to the left branch of the right child, times the probability $p$ that the right branch of the left child is identical to the right branch of the right child. That guarantees that the left and right child are identical, and as I argued, that they're identical has the same probability as that they're mirror images. $\endgroup$
    – joriki
    Commented Feb 20, 2023 at 10:59
  • $\begingroup$ Understood. I didn't like this approach because the definition of $p$ seems to be varied from root node to left and right node: initially $p$ is branches of "same node" mirror now braches of "two node" mirror. The problem with that is when you do $p^2$, I always have a hunch that the no-child cases get double counted. $\endgroup$
    – Albert
    Commented Feb 20, 2023 at 14:27
  • $\begingroup$ Btw, my approach is just taking one more step further from yours and it yields the same result. $\endgroup$
    – Albert
    Commented Feb 20, 2023 at 14:28
  • $\begingroup$ @Albert: I don't understand what you wrote about the definition being varied. In all cases, $p$ is the probability that two branches are identical. Mirroring never plays a role; $p$ is defined from the very beginning as the probability of two branches being identical; the only mention of mirroring is the argument that the root node's two branches being mirror images is the same as the probability of its two branches being identical. $\endgroup$
    – joriki
    Commented Feb 20, 2023 at 14:46

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .